Hybrids of integer programming and ACO for resource constrained job scheduling

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.