Scheduling jobs on batch machines to reduce late work time
Serial-batch scheduling to minimise the total weighted late work
Data Structures and Algorithms
Summary
This paper looks at how to schedule jobs on a machine that processes batches of jobs one after another. Each batch requires some setup time before it starts, and jobs inside the batch finish together after all have been processed. The authors found this scheduling problem is very hard to solve perfectly in general. They created step-by-step procedures (dynamic programming algorithms) that can solve the problem efficiently for some special cases. Their methods are faster than a popular commercial solver in tests.
What this means in practice
- •For manufacturing planners: Optimize job orders on batch-processing machines to reduce delay penalties under fixed due dates.
- •For logistics coordinators: Schedule sequential group tasks with setup delays to minimize overall late work impact in delivery pipelines.
Authors
Yao-Wen Sang, Naiming Xie, Jian Chen, Malgorzata Sterna, Jacek Blazewicz
Abstract
We study the problem of scheduling jobs on a serial-batch machine with the aim of minimising the total weighted late work. In a serial-batch setting, jobs within a batch are processed sequentially, and none are removed from the machine until the last job in the batch completes its processing. The processing time of a batch is the sum of the processing times of the jobs within it, and the completion time for each job in the batch is equal to the makespan of the jobs in the batch. When a new batch begins, a constant setup time is required for the machine. We show that minimising the total weighted late work in this environment is $NP$-hard even if all jobs have a common due date and unit weight. For the general problem, we present a pseudo-polynomial time dynamic programming algorithm. Additionally, we explore two special cases, i.e., one with a common due date and another with an agreeable condition among due dates, processing times and weights. For both special cases, we develop specialised pseudo-polynomial time dynamic programming algorithms. The proposed approaches are equipped with specialised acceleration techniques to enhance their computational performance. The extended experiments demonstrate that the dynamic programming algorithms outperform Gurobi in time efficiency.