Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4627163 | Applied Mathematics and Computation | 2015 | 7 Pages |
Abstract
We consider the single machine scheduling problem with release dates and tails, provided that the machine is unavailable during a fixed interval. We aim to minimize the maximum delivery time under the nonresumable senario. This problem is strongly NP-hard. The proposed algorithm is based on a branch-and-bound method. We use Jackson’s preemptive algorithm with precedence constraints to compute the lower bound and Schrage’s sequence as an upper bound. Numerical experiments show that the algorithm can solve large-size instances with up to 1000 jobs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Walid Hfaiedh, Chérif Sadfi, Imed Kacem, Atidel Hadj-Alouane,