Single-machine batch delivery scheduling and common due-date assignment with a rate-modifying activity

Abstract

We consider batch delivery scheduling on a single machine, where a common due-date is assigned to all the jobs and a rate-modifying activity on the machine may be scheduled, which can change the processing rate of the machine. Thus the actual processing time of a job is variable depending on whether it is processed before or after the rate-modifying activity. The objective is to determine the optimal job sequence, the optimal partition of the job sequence into batches, the optimal assigned common due-date, and the optimal location of the rate-modifying activity simultaneously to minimize the total cost of earliness, job holding, weighted number of tardy jobs, due-date assignment, and batch delivery. We derive some structural properties of the problem, based on which we design polynomial-time algorithms to solve some special cases of the problem.

Keywords:

• scheduling
• common due-date assignment
• batching
• rate-modifying activity

Acknowledgements

We sincerely thank the Editor, an AE, and two anonymous referees for their valuable comments on earlier versions of our paper.

Notes

1 This paper was supported in part by the National Natural Science Foundation of China [grand number 71301022]; by the Natural Science Foundation of Jiangxi, China [grand number 20132BAB201010]; by the Science Foundation of Education Committee of Jiangxi, China [grand number GJJ13458]; and by the NSC of Taiwan [grand number NSC 102-2410-H-035-034], [grand number NSC 102-2221-E-035-070-MY3].