A time-indexed LP-based approach for min-sum job-shop problems |
| |
Authors: | Giuseppe Lancia Franca Rinaldi Paolo Serafini |
| |
Institution: | 1.Department of Mathematics and Computer Science,University of Udine,Udine,Italy |
| |
Abstract: | In this paper we propose two time-indexed IP formulations for job-shop scheduling problems with a min-sum objective. The first
model has variables associated to job scheduling patterns. The exponential number of variables calls for a column generation
scheme which is carried out by a dynamic programming procedure. The second model is of network flow type with side constraints.
This model can be strengthened by adding cutting inequalities of clique type. It turns out that the two models are equivalent,
since the dual of the second formulation is equivalent to the compact dual of the first model. However, they require significantly
different solution approaches and may behave differently in terms of computing time and memory usage. Good upper bounds are
found by a heuristic procedure that randomly generates schedules from fractional solutions. These features allow for an effective
pruning of the branch-and-bound tree and narrowing the gap between lower and upper bounds. However, the size of both models
is critically affected by the time-indexed formulation which may heavily slow down the computation. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|