[en] This paper studies the permutation flowshop scheduling problem with sequence dependent setup times and time lags constraints minimizing the number of tardy jobs. Dependent setup times are defined as the work to prepare the machines between two successive jobs. Time lags are defined as intervals of time that must exist between every couple of successive operations of the same job. Two mathematical programming formulations are proposed for the considered problem. A simulated annealing algorithm is also developed to solve the problem. Computational experiments are presented and discussed.
Research center :
CRTI - Centre de Recherche en Technologie de l'Information
Disciplines :
Quantitative methods in economics & management Mathematics
Author, co-author :
Dhouib, E.
Teghem, Jacques ; Université de Mons > Faculté Polytechnique > Mathématique et Recherche opérationnelle
Loukil, T.
Language :
English
Title :
Minimizing the Number of Tardy Jobs in a Permutation Flowshop Scheduling Problem with Setup Times and Time Lags Constraints
Publication date :
01 March 2013
Journal title :
Journal of Mathematical Modelling and Algorithms
ISSN :
1570-1166
Publisher :
Kluwer Academic Publishers, Netherlands
Volume :
12
Issue :
1
Pages :
85-99
Peer reviewed :
Peer reviewed
Research unit :
F151 - Mathématique et Recherche opérationnelle
Research institute :
R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique
Allahverdi, A., Gupta, J. N. D., Aldowaisan, T.: A review of scheduling research involving setup considerations. OMEGA, Int. J. Manage. Sci. 27, 219-239 (1999).
Allahverdi, A., Al-Anzi, F.: Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications. Comput. Oper. Res. 29, 971-994 (2002).
Allahverdi, A., Ng, C. T., Cheng, T. C. E., Kovalyov, M. Y.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187, 985-1032 (2008).
Brucker, P., Knust, S., Cheng, T. C. E., Shakhlevich, N. V.: Complexity results for flowshop and open shop scheduling problems with transportation delays. Ann. Oper. Res. 129, 81-106 (2004).
Bulfin, R. L., M'Hallah, R.: Minimizing the weighted number of tardy jobs on a two-machine flowshop. Comput. Oper. Res. 30, 1887-1900 (2003).
Corce, F. D., Gupta, J. N. D., Tadei, R.: Minimizing tardy jobs in a flowshop with common due date. Eur. J. Oper. Res. 120, 375-381 (2000).
Fondrevelle, J., Oulamara, A., Portmann, M-C.: Permutation flowshop scheduling problems with maximal and minimal time lags. Comput. Oper. Res. 33, 1540-1556 (2006).
Fondrevelle, J., Oulamara, A., Portmann, M.-C.: Permutation flowshop scheduling problems with time lags to minimize the weighted sum of machine completion times. Int. J. Prod. Econ. 112, 168-176 (2008).
Fortemps, Ph., Ost, Ch., Pirlot, M., Teghem, J., Tuyttens, D.: Using metaheuristics for solving a production scheduling problem in a chemical firm: a case study. Int. J. Prod. Econ. 46-47, 13-26 (1996).
Hariri, A. M. A., Potts, C. N.: A branch and bound algorithm to minimize the number of late jobs in a permutation flowshop. Eur. J. Oper. Res. 38, 228-237 (1989).
Johnson, S. M.: Optimal two-and-three-stage production schedules with setup times included. Nav. Res. Logist. Q. 1, 61-68 (1954).
Khurana, K., Bagga, P. C.: Minimizing the makespan in a two-machine fowshop with time lags and setup conditions. Z. Oper. Res. 28, 163-174 (1984).
Kirkpatrick, S., Gelatt, J. C., Vecchi, M.: Optimisation by simulated annealing. Manage. Sci. 220, 498-516 (1983).
Koulamas, C.: On the complexity of two-machine flowshop problems with due date related objectives. Eur. J. Oper. Res. 106, 95-100 (1998).
Lawler, E. L., Moore, J. M.: A functional equation and its application to resource allocation and sequencing problems. Manage. Sci. 15, 102-109 (1968).
Moore, J. M.: An n job, one machine algorithm for minimizing the number of late jobs. Manage. Sci. 15, 102-109 (1968).
Munier-Kordon, A., Rebaine, D.: Polynomial time algorithms for the UET permutation flowshop problem with time delays. Comput. Oper. Res. 35, 525-537 (2008).
Parthasarathy, S., Rajendran, C.: An experimental evaluation of heuristics for scheduling in a real-life flowshop with sequence dependent setup times of jobs. Int. J. Prod. Econ. 49, 255-263 (1997).
Rios-Mercado, R. Z., Bard, J. F.: Computational Experience with a branch-and-cut algorithm for flowshop scheduling with setups. Comput. Oper. Res. 25, 351-366 (1998).
Ruiz, R., Maroto, C., Alcaraz, J.: Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics. Eur. J. Oper. Res. 165, 34-54 (2005).
Stafford, E. F., Tseng, F. T.: Two models for a family of flowshop sequencing problems. Eur. J. Oper. Res. 142, 282-293 (2002).
Szwarc, W.: The flowshop problem with time lags and separated setup times. ZOR-Z. Oper. Res. 30, 15-22 (1986).
Teghem, J., Pirlot, M.: Optimisation Approchée en Recherche Opérationnelle. Hermes Science Publications, Paris (2002).
Yang, D. L., Chern, M. S.: A two-machine flowshop sequencing problem with limited waiting time constraints. Comput. Ind. Eng. 28, 63-70 (1995).
