Minimizing the Number of Late Jobs under the Group Technology Assumption |
| |
Authors: | Zhaohui Liu Wenci Yu |
| |
Institution: | (1) Institute of Applied Mathematics, East China University of Science and Technology, Shanghai, 200237, China |
| |
Abstract: | We consider the one-machine scheduling problem to minimize the number of late jobs under the group technology assumption, where jobs are classified into groups and all jobs from the same group must be processed contiguously. This problem is shown to be strongly NP-hard, even for the case of unit processing time and zero set-up time. A polynomial time algorithm is developed for the restricted version in which the jobs in each group have the same due date. However, the problem is proved to be ordinarily NP-hard if the jobs in a group have the same processing time as well as the same due date. |
| |
Keywords: | one-machine scheduling group technology number of late jobs NP-hardness polynomial algorithm |
本文献已被 SpringerLink 等数据库收录! |
|