Article ID: | iaor20063298 |
Country: | United Kingdom |
Volume: | 32 |
Issue: | 12 |
Start Page Number: | 3265 |
End Page Number: | 3271 |
Publication Date: | Dec 2005 |
Journal: | Computers and Operations Research |
Authors: | epek Ondej, Sung Shao Chin |
Keywords: | optimization, production: JIT |
In this paper, we study a scheduling problem on identical parallel machines, in which a processing time and a due date are given for each job, and the objective is to maximize the number of just-in-time jobs. A job is called just-in-time if it is completed exactly on its due date. We discuss the known results, show that a recently published greedy algorithm for this problem is incorrect, and present a new quadratic time algorithm which solves the problem.