A note on parallel-machine due-window assignment

Abstract

We consider a due-window assignment problem on identical parallel machines, where the jobs have equal processing times and job-dependent earliness-tardiness costs. We would like to determine a ‘due window’ during which the jobs can be completed at no cost and to obtain a job schedule in which the jobs are penalized if they finish before or after the due window. The objective is to minimize the total earliness and tardiness job penalty, plus the cost associated with the size of the due window. We present an algorithm that can solve this problem in O(n³) time, which is an improvement of the O(n⁴) solution procedure developed by Mosheiov and Sarig.

Keywords:

• scheduling
• parallel machines
• earliness-tardiness
• due window
• assignment problem

Acknowledgements

This research was supported in part by The Hong Kong Polytechnic University under grant J-BB7H. The first author was also supported in part by the National Natural Science Foundation of China under grant 71001109 and by the Ministry of Education of the PRC under grant 09YJC630235. The third author was also supported in part by the National Natural Science Foundation of China under grant 10971187.