Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
Single machine scheduling to maximize the number of on-time jobs with generalized due-dates
Ist Teil von
Journal of scheduling, 2020-06, Vol.23 (3), p.289-299
Ort / Verlag
New York: Springer US
Erscheinungsjahr
2020
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
In scheduling problems with generalized due dates (gdd), the due dates are specified according to their position in the sequence, and the
j
-th due date is assigned to the job in the
j
-th position. We study a single-machine problem with generalized due dates, where the objective is maximizing the number of jobs completed exactly on time. We prove that the problem is NP-hard in the strong sense. To our knowledge, this is the only example of a scheduling problem where the job-specific version has a polynomial-time solution, and the gdd version is strongly NP-hard. A branch-and-bound (B&B) algorithm, an integer programming (IP)-based procedure, and an efficient heuristic are introduced and tested. Both the B&B algorithm and the IP-based solution procedure can solve most medium-sized problems in a reasonable computational effort. The heuristic serves as the initial step of the B&B algorithm and in itself obtains the optimum in most cases. We also study two special cases: max-on-time for a given job sequence and max-on-time with unit-execution-time jobs. For both cases, polynomial-time dynamic programming algorithms are introduced, and large-sized problems are easily solved.