Abstract
This paper deals with the two-machine total completion time flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the positional completion times integer programming formulation of the problem with O(n 2) variables and O(n) constraints.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akkan, C., & Karabati, S. (2004). The two-machine flowshop total completion time problem: Improved lower bounds and a branch-and-bound algorithm. European Journal of Operational Research, 159, 420–429.
Bansal, S. P. (1977). Minimizing the sum of completion times of n-jobs over M-machines in a flowshop. A branch and bound approach. AIIE Transactions, 9, 306–311.
Czapiński, M. (2010). Parallel simulated annealing with genetic enhancement for flowshop problem with C sum . Computers & Industrial Engineering, 59, 778–785.
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.
Della Croce, F., Ghirardi, M., & Tadei, R. (2004). Recovering beam search: enhancing the beam search approach for combinatorial optimization problems. Journal of Heuristics, 10, 89–104.
Della Croce, F., Grosso, A., & Salassa, F. (2011). A matheuristic approach for the total completion time two-machines permutation flow shop problem. In Lecture notes in computer science: Vol. 6622. Proceedings of EvoCop 2011 (pp. 38–47), Torino, Italy, April 27–29, 2011.
Della Croce, F., Narayan, V., & Tadei, R. (1996). The two-machine total completion time flow shop problem. European Journal of Operational Research, 90, 227–237.
Della Croce, F., & Salassa, F. (2008). A variable neighborhood search based matheuristic for nurse rostering problems. In PATAT 2010 proceedings, 8th international conference on the practice and theory of automated timetabling (pp. 167–175), Belfast (UK), 10–13 August 2010.
Dong, X., Huang, H., & Chen, P. (2009). An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion. Computers & Operations Research, 36, 1664–1669.
Fischetti, M., & Lodi, A. (2003). Local branching. Mathematical Programming B, 98, 23–47.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1, 117–129.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Operation Research, 5, 287–326.
Hansen, P., & Mladenovic, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130, 449–467.
Hoogeveen, H., van Norden, L., & van de Velde, S. (2006). Lower bounds for minimizing total completion time in a two-machine flow shop. Journal of Scheduling, 9, 559–568.
Hoogeveen, J. A., & Van de Velde, S. L. (1995). Stronger Lagrangian bounds by use of slack variables: applications to machine scheduling problems. Mathematical Programming, 70, 173–190.
Ladhari, T., & Rakrouki, M. A. (2009). Heuristics and lower bounds for minimizing the total completion time in a two-machine flowshop. International Journal of Production Economics, 122, 678–691.
Lasserre, J. B., & Queyranne, M. (1992). Generic scheduling polyhedral and a new mixed integer formulation for single machine scheduling. In Proceedings of the IPCO conference (pp. 136–149).
Maniezzo, V., Stutzle, T., & Voss, S. (2009). Annals of information systems: Vol. 10. Matheuristics: hybridizing metaheuristics and mathematical programming. Berlin: Springer.
Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165, 479–494.
Stafford, E. F. (1988). On the development of a mixed integer linear programming model for the flowshop sequencing problem. The Journal of the Operational Research Society, 39, 1163–1174.
Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47, 65–74.
Van de Velde, S. (1990). Minimizing the sum of job completion times in the two-machine flowshop by Lagrangean relaxation. Annals of Operation Research, 26, 257–268.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Della Croce, F., Grosso, A. & Salassa, F. A matheuristic approach for the two-machine total completion time flow shop problem. Ann Oper Res 213, 67–78 (2014). https://doi.org/10.1007/s10479-011-0928-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-011-0928-x