Hybrids of integer programming and ACO for resource constrained job scheduling

Dhananjay Raghavan Thiruvady, Gaurav Singh, Andreas Tilman Ernst

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

11 Citations (Scopus)

Abstract

A recent line of research considers hybrids of Lagrangian relaxation and Ant Colony Optimisation (ACO). Studies have shown that for hard constrained optimisation problems Lagrangian relaxation can effectively guide ACO to provide good feasible solutions. We consider applying these ideas to create a matheuristic combining ACO with decomposition approaches from mathematical programming for a resource constrained job scheduling problem. We are given a number of jobs which have to be executed on a number of machines satisfying several constraints. These include precedences and release times within machines and the machines are linked via a central resource constraint. By removing the linking constraint, the each machine’s scheduling problem can be solved independently as a relatively simple subproblem. Both Danzig-Wolfe decomposition with column generation and Lagrangian relaxation are tried to carry out this decomposition. The relaxed solutions can provide useful guidance to determine solutions either via problem specific heuristics and ACO. Empirical results show that the Lagrangian relaxation matheuristic performs well in limited time-frames whereas the column generation based heuristic provides improved lower and upper bounds when run to convergence.
Original languageEnglish
Title of host publicationHybrid Metaheuristics
EditorsMaria J Blesa, Christian Blum, Stefan Voss
Place of PublicationHeidelberg Germany
PublisherSpringer
Chapter10
Pages130-144
Number of pages15
Volume8457
ISBN (Print)9783319076430
DOIs
Publication statusPublished - 2014
Externally publishedYes
EventInternational Workshop on Hybrid Metaheuristics (HM) 2014 - Hamburg, Germany
Duration: 11 Jun 201413 Jun 2014
Conference number: 9th
http://www.springer.com/gp/book/9783319076430

Workshop

WorkshopInternational Workshop on Hybrid Metaheuristics (HM) 2014
Abbreviated titleHM 2014
CountryGermany
CityHamburg
Period11/06/1413/06/14
Internet address

Cite this