A Matheuristic Based on Column Generation for Parallel Machine Scheduling with Sequence Dependent Setup Times

Filipe Alvelos (), Manuel Lopes () and Henrique Lopes
Additional contact information
Filipe Alvelos: Universidade do Minho
Manuel Lopes: Polytechnic of Porto
Henrique Lopes: Universidade do Minho

A chapter in Computational Management Science, 2016, pp 233-238 from Springer

Abstract: Abstract In this paper we propose a heuristic approach based on column generation (CG) and a general purpose integer programming (GPIP) solver to address a scheduling problem. The problem consists in scheduling independent jobs with given processing times on unrelated parallel machines with sequence-dependent setup times. The objective is to minimize the total weighted tardiness. The proposed matheuristic (MH) takes advantage of the efficiency of CG to define a (restricted) search space which is explored by a GPIP solver. In different iterations, different additional constraints are introduced in CG, allowing the definition of several (restricted) search spaces to be explored by the GPIP solver. Computational results show that the proposed MH can be used to tackle very large instances (e.g. 100 machines and 400 jobs) obtaining better solutions in less time than a state-of-the-art branch-and-price algorithm from the literature.

Keywords: Sequence-dependent Setup Times; Column Generation (CG); General Purpose Integer Programming (GPIP); Parallel Machine Scheduling Problem; Restricted Master Problem (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:lnechp:978-3-319-20430-7_30

Ordering information: This item can be ordered from
http://www.springer.com/9783319204307

DOI: 10.1007/978-3-319-20430-7_30

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().