Article ID: | iaor2012374 |
Volume: | 34 |
Issue: | 1 |
Start Page Number: | 43 |
End Page Number: | 68 |
Publication Date: | Jan 2012 |
Journal: | OR Spectrum |
Authors: | Kis Tams, Kovcs Andrs |
Keywords: | scheduling, programming: linear, combinatorial optimization |
Bilevel scheduling problems constitute a hardly studied area of scheduling theory. In this paper, we summarise the basic concepts of bilevel optimisation, and discuss two problem classes for which we establish various complexity and algorithmic results. The first one is the bilevel total weighted completion time problem in which the leader assigns the jobs to parallel machines and the follower sequences the jobs assigned to each machine. Both the leader and the follower aims to minimise the total weighted completion time objective, but with different job weights. When the leader’s weights are arbitrary, the problem is NP‐hard. However, when all the jobs are of unit weight for the leader, we provide a heuristic algorithm based on iterative LP‐rounding along with computational results, and provide a sufficient condition when the LP‐solution is integral. In addition, if the follower weights induce a monotone (increasing or decreasing) processing time order in any optimal solution, the problem becomes polynomially solvable. As a by‐product, we characterise a new polynomially solvable special case of the MAX