Paper Info
Title
A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times
Abstract
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.
Year
DOI
Venue
2010
10.1016/j.cor.2009.07.006
Computers & OR
Keywords
DocType
Volume
non-delayed relax-and-cut algorithm,reasonable time,interesting gap,approximate solution,due date,unrelated parallel machine,Lagrangean relaxation,Lagrangean heuristic,sequence-dependent setup time,associated processing time
Journal
37
Issue
ISSN
Citations 
5
Computers and Operations Research
6
PageRank 
References 
Authors
0.43
19
3
Name
Order
Citations
PageRank
Mateus Rocha de Paula160.43
Geraldo Robson Mateus241342.30
Martín Gómez Ravetti3576.63