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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job-shop scheduling. Management Science, 34, 391–401.
Back, J. C., Feng, T. K., & Watson, J.-P. (2011). Combining constraint programming and local search for job-shop scheduling. INFORMS Journal on Computing, 23(1). doi: 10.1287/ijoc.1100.0388
Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based scheduling. Berlin: Springer.
Baptiste, P., Flamini, M., & Sourd, F. (2008). Lagrangian bounds for just-in-time job-shop scheduling. Computers & Operations Research, 35, 906–915.
Blażewicz, J., Domschke, W., & Pesch, E. (1996). The job shop scheduling problem: conventional and new solution techniques. European Journal of Operational Research, 93, 1–33.
Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems: algorithms and applications. European Journal of Operational Research, 119, 557–581.
Brucker, P. (2007a) Scheduling Algorithms (5th ed.). Berlin: Springer.
Brucker, P. (2007b). The job-shop problem: old and new challenges. In P. Baptiste, G. Kendall, A. Munier-Kordon, & F. Sourd (Eds.), Proceedings of the MISTA conference 2007 (pp. 15–22).
Carr, R. D., & Lancia, G. (2002). Compact vs exponential-size LP relaxations. Operations Research Letters, 30(1), 57–65.
Chakrabarti, S., Phillips, C., Schulz, A., Shmoys, D., Stein, C., & Wein, J. (1996). Improved scheduling algorithms for minsum criteria. In Proceedings of the 23rd international colloquium on automata, languages and programming (pp. 646–657). Berlin: Springer.
Chen, A., & Luh, P. (2003). An alternative framework to Lagrangian relaxation approach for job shop scheduling. European Journal of Operational Research, 149, 499–512.
Chen, H., Chu, C., & Proth, J. M. (1998). An improvement of the Lagrangean relaxation approach for job shop scheduling: a dynamic programming method. IEEE Transactions on Robotics and Automation, 14, 786–795.
Della Croce, F., Ghirardi, M., & Tadei, R. (2002). An improved branch-and-bound algorithm for the two machine total completion time flow shop problem. European Journal of Operational Research, 139, 293–301.
Dorndorf, U., Pesch, U. E., & Phan-Huy, T. (2002). Constraint propagation and problem decomposition: a preprocessing procedure for the job shop problem. Annals of Operation Research, 115, 125–145.
Dyer, M. E., & Wolsey, L. A. (1990). Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics, 26, 255–270.
Grötschel, M., Lovász, L., & Schrijver, A. (1993). Geometric algorithms and combinatorial optimization. Berlin: Springer.
Jain, A. S., & Meeran, S. (1999). Deterministic job-shop scheduling: past, present and future. European Journal of Operational Research, 113, 390–434.
Lageweg, B. J., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1977). Job-shop scheduling by implicit enumeration. Management Science, 34, 441–450.
Lancia, G., Rinaldi, F., & Serafini, P. (1999). A column generation approach to solve job-shop problems. In IFORS99 conference (p. 11). Final Program, Beijing, P.R. China, August 16–20.
Lancia, G., Rinaldi, F., & Serafini, P. (2007). A compact optimization approach to solve job-shop problems. In P. Baptiste, G. Kendall, A. Munier-Kordon, & F. Sourd (Eds.), Proceedings of the MISTA conference 2007 (pp. 293–300).
Maniezzo, V., Stützle, T., & Voßeds, S. (2010). Hybridizing metaheuristics and mathematical programming. Berlin: Springer.
Martin, K. (1991). Using separation algorithms to generate mixed integer model reformulations. Operations Research Letters, 10, 119–128.
Nowicki, E., & Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8, 145–159.
Potts, C. N., & Strusevich, V. A. (2009). Fifty years of scheduling: a survey of milestones. The Journal of the Operational Research Society, 60, S41–S68.
Queyranne, M., & Sviridenko, M. (2002). Approximation algorithms for shop scheduling problems with minsum objective. Journal of Scheduling, 5, 287–305.
Savelsbergh, M. W. P., Uma, R. N., & Wein, J. (2005). An experimental study of LP-based approximation algorithms for scheduling problems. INFORMS Journal on Computing, 17, 123–136.
Vaessens, R. J. M., Aarts, E. H. L., & Lenstra, J. K. (1996). Job shop scheduling by local search. INFORMS Journal on Computing, 8, 302–317.
Van den Akker, J. M., Hoogeveen, H., & Van de Velde, S. (1997). Parallel machine scheduling by column generation. Operations Research, 47, 862–872.
Van den Akker, J. M., Huskens, C. A. J., & Savelsbergh, M. W. P. (2000). Time-indexed formulations for machine scheduling problems: column generation. INFORMS Journal on Computing, 12, 111–124.
Watson, J. P., Barbulescu, L., Howe, A. E., & Whitley, L. D. (1999) Algorithm performance and problem structure for flow-shop scheduling. In Proceedings of the sixteenth national conference on artificial intelligence (pp. 688–695).
Zhang, C. Y., Li, P. G., Rao, Y. Q., & Guan, Z. L. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers & Operations Research, 35, 282–294.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lancia, G., Rinaldi, F. & Serafini, P. A time-indexed LP-based approach for min-sum job-shop problems. Ann Oper Res 186, 175–198 (2011). https://doi.org/10.1007/s10479-010-0832-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-010-0832-9