A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times

摘要

Consider the problem of scheduling a set of jobs to be processed exactly once, on any machine of a set ofrnunrelated parallel machines, without preemption. Each job has a due date, weight, and, for each machine,rnan associated processing time and sequence-dependent setup time. The objective function considered isrnto minimize the total weighted tardiness of the jobs.rnThis work proposes a non-delayed relax-and-cut algorithm, based on a Lagrangean relaxation of a timernindexed formulation of the problem. A Lagrangean heuristic is also developed to obtain approximaternsolutions.rnUsing the proposed methods, it is possible to obtain optimal solutions within reasonable time for somerninstances with up to 180 jobs and six machines. For the solutions for which it is not possible to provernoptimality, interesting gaps are obtained.