Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost

作者：Geng, Zhichao; Yuan, Jinjiang; Yuan, Junling

来源：Applied Mathematics and Computation, 2018, 332: 1-18.

DOI：10.1016/j.amc.2018.03.001

• Scheduling
• Pareto optimization
• Serial-batch
• Maximum cost
• Makespan

In this paper, we consider several scheduling problems on a serial-batch machine for scheduling jobs with or without precedence relations. Under the serial-batch setting, the jobs in a batch are processed in succession and are removed until the last job in this batch finishes its processing. Thus, the processing time of a batch is equal to the sum of processing times of jobs in the batch. When a new batch starts, a constant setup time is required for the machine. The objectives of the problems involve minimizing makespan and a maximum cost. For these problems, we either present polynomial-time algorithms to generate all Pareto optimal points and find a corresponding Pareto optimal schedule for each Pareto optimal point, or give the strong NP-hardness proof. Experimentation results show that the proposed algorithms for the considered problems are very efficient.

• 出版日期2018-9-1
• 单位郑州大学; 郑州轻工业大学