A polynomial algorithm for special case of the one-machine scheduling problem with time-lags

Helena Ramalhinho-Lourenço ()
Additional contact information
Helena Ramalhinho-Lourenço: https://www.upf.edu/web/econ/faculty/-/asset_publisher/6aWmmXf28uXT/persona/id/3418484

Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra

Abstract: 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.

Keywords: One-machine scheduling; polynomial algorithms; lower bounds (search for similar items in EconPapers)
JEL-codes: C61 C63 (search for similar items in EconPapers)
Date: 1998-12
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://econ-papers.upf.edu/papers/339.pdf Whole Paper (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:upf:upfgen:339

Access Statistics for this paper

More papers in Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra
Bibliographic data for series maintained by ( this e-mail address is bad, please contact ).