On-line Batch Scheduling on Tow Parallel Machines With Wait
It was studied with the problem of scheduling jobs in batches on-line on 2 identical parallel machines with objective to minimize the maximum completion time (the completion time of the last job: makespan),where batches arrive over list and every batch has exactly m jobs,and the processing times are constrained in some interval.When a batch arrives we schedule the jobs in this batch immediately and irrevocably without the knowledge of later batches.The pre-emption is not allowed.An algorithm with scheduling jobs in every batch by LPT rule was proposed.When all the jobs in pre-batch are scheduled we schedule the jobs in the following batch.The worst case was analyzed and the worst case ratio dependent with number of jobs in batch was given,and the conclusion was proved by procedure.
batch on-line List Schedule competitive ratio identical parallel machines batch list maximum completion time processing time
HUO Manchen CHEN Zhongjiu
Shenyang Engineering Institute organization Shenyang, China Liaoning Administrators College of Police and Justice Shenyang, China
国际会议
重庆
英文
776-779
2015-12-19（万方平台首次上网日期，不代表论文的发表时间）