A polynomial algorithm for special case of the one-machine scheduling problem with time-lags
The standard one-machine scheduling problem consists in scheduling a set of jobs in one machine which can handle only one job at a time, minimizing the maximum lateness. Each job is available for processing at its release date, requires a known processing time and after finishing the processing, it is delivery after a certain time. There also can exists precedence constraints between pairs of jobs, requiring that the first jobs must be completed before the second job can start. An extension of this problem consists in assigning a time interval between the processing of the jobs associated with the precedence constrains, known by finish-start time-lags. In presence of this constraints, the problem is NP-hard even if preemption is allowed. In this work, we consider a special case of the one-machine preemption scheduling problem with time- lags, where the time-lags have a chain form, and propose a polynomial algorithm to solve it. The algorithm consist in a polynomial number of calls of the preemption version of the Longest Tail Heuristic. One of the applicability of the method is to obtain lower bounds for NP-hard one-machine and job-shop scheduling problems. We present some computational results of this application, followed by some conclusions.
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Carlier, Jacques, 1982. "The one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 11(1), pages 42-47, September.
When requesting a correction, please mention this item's handle: RePEc:upf:upfgen:339. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ()
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.