Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/923208

OpenURL Link
Title
A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times
Author/Creator
de Paula, Mateus Rocha;  Mateus, Geraldo Robson;  Ravetti, Martín Gómez
Institution
The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description
Consider the problem of scheduling a set of jobs to be processed exactly once, on any machine of a set of unrelated parallel machines, without preemption. Each job has a due date, weight, and, for each machine, an associated processing time and sequence-dependent setup time. The objective function considered is to minimize the total weighted tardiness of the jobs. This work proposes a non-delayed relax-and-cut algorithm, based on a Lagrangean relaxation of a time indexed formulation of the problem. A Lagrangean heuristic is also developed to obtain approximate solutions. Using the proposed methods, it is possible to obtain optimal solutions within reasonable time for some instances with up to 180 jobs and six machines. For the solutions for which it is not possible to prove optimality, interesting gaps are obtained.
Relation
Computers and Operations Research Vol. 37, Issue 5, p. 938-949
Publisher Link
http://dx.doi.org/10.1016/j.cor.2009.07.006
Date
2010
Publisher
Elsevier
Keyword(s)
scheduling problems;  parallel machines;  Lagrangean relaxation;  relax-and-cut
Resource Type
journal article
Identifier
http://hdl.handle.net/1959.13/923208
Identifier
ISSN:0305-0548
Reviewed
Reviewed
20 Visitors 22 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"Computers and Operations Research"
 
OR