关键词: bicriteria scheduling, series-batching, makespan, total weighted completion time, Pareto optimal schedules

Abstract: 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. 

Key words: bicriteria scheduling, series-batching, makespan, total weighted completion time, Pareto optimal schedules