Bicriteria Scheduling on a Series-Batching Machine to Minimize Makespan and Total Weighted Completion Time with Equal Length Job  

作　　者：HE Cheng LIN Hao DO U Jun-mei MU Yun-dong 

机构地区：[1]School of Science, Henan University of Technology, Zhengzhou 450001, China

出　　处：《Chinese Quarterly Journal of Mathematics》2014年第2期159-166,共8页数学季刊（英文版）

基　　金：Foundation item： Supported by the National Natural Science Foundation of China（11201121, 11101383）; Supported by the China Scholarship Counci1（201309895008）; Supported bythe 2013GGJS-079; Supported by the 2011B110008

摘　　要：It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b ≥ n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O(n3) time.It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b≥n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O（n3） time.

关 键 词：BICRITERIA SCHEDULING series-batching MAKESPAN total weighted completiontime Pareto optimal schedules 

分 类 号：O221.6[理学—运筹学与控制论]