Welcome to the UPF Digital Repository

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

Show simple item record

dc.contributor.author Ramalhinho-Lourenço, Helena
dc.contributor.other Universitat Pompeu Fabra. Departament d'Economia i Empresa
dc.date.accessioned 2017-07-26T10:50:31Z
dc.date.available 2017-07-26T10:50:31Z
dc.date.issued 1998-12-01
dc.identifier https://econ-papers.upf.edu/ca/paper.php?id=339
dc.identifier.uri http://hdl.handle.net/10230/376
dc.description.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.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.relation.ispartofseries Economics and Business Working Papers Series; 339
dc.rights L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.title A polynomial algorithm for special case of the one-machine scheduling problem with time-lags
dc.type info:eu-repo/semantics/workingPaper
dc.date.modified 2017-07-23T02:04:09Z
dc.subject.keyword one-machine scheduling
dc.subject.keyword polynomial algorithms
dc.subject.keyword lower bounds
dc.subject.keyword Operations Management
dc.rights.accessRights info:eu-repo/semantics/openAccess


This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account


In collaboration with Compliant to Partaking