ISSN:
1573-2886
Keywords:
one-machine scheduling
;
group technology
;
number of late jobs
;
NP-hardness
;
polynomial algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009841719644
Permalink