A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines |
| |
| Authors: | Ond&#x;ej epek Shao Chin Sung |
| |
| Affiliation: | aDepartment of Theoretical Informatics and Mathematical Logic, Charles University, Malostranské nám. 25, 1118 00 Praha 1, Czech Republic;bSchool of Information Science, Japan Advanced Institute of Science and Technology 1-1 Asahidai, Tatsunokuchi, Ishikawa 923-1292, Japan |
| |
| Abstract: | 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. |
| |
| Keywords: | Scheduling Identical parallel machines Just-in-time jobs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
