Skip to main content
SpringerLink
Log in

Minimizing the Number of Tardy Jobs in a Permutation Flowshop Scheduling Problem with Setup Times and Time Lags Constraints

  • Published:
Journal of Mathematical Modelling and Algorithms in Operations Research

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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)

    Article  Google Scholar 

  2. 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)

    Article  MATH  Google Scholar 

  3. 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)

    Article  MathSciNet  MATH  Google Scholar 

  4. 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)

    Article  MathSciNet  MATH  Google Scholar 

  5. 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)

    Article  MathSciNet  MATH  Google Scholar 

  6. 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)

    Article  Google Scholar 

  7. Fondrevelle, J., Oulamara, A., Portmann, M-C.: Permutation flowshop scheduling problems with maximal and minimal time lags. Comput. Oper. Res. 33, 1540–1556 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. 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)

    Article  Google Scholar 

  9. 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)

    Article  Google Scholar 

  10. 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)

    Article  MathSciNet  MATH  Google Scholar 

  11. Johnson, S.M.: Optimal two-and-three-stage production schedules with setup times included. Nav. Res. Logist. Q. 1, 61–68 (1954)

    Article  Google Scholar 

  12. 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)

    MathSciNet  MATH  Google Scholar 

  13. Kirkpatrick, S., Gelatt, J.C., Vecchi, M.: Optimisation by simulated annealing. Manage. Sci. 220, 498–516 (1983)

    MathSciNet  Google Scholar 

  14. Koulamas, C.: On the complexity of two-machine flowshop problems with due date related objectives. Eur. J. Oper. Res. 106, 95–100 (1998)

    Article  Google Scholar 

  15. Lawler, E.L., Moore, J.M.: A functional equation and its application to resource allocation and sequencing problems. Manage. Sci. 15, 102–109 (1968)

    Article  Google Scholar 

  16. Moore, J.M.: An n job, one machine algorithm for minimizing the number of late jobs. Manage. Sci. 15, 102–109 (1968)

    Article  MATH  Google Scholar 

  17. Munier-Kordon, A., Rebaine, D.: Polynomial time algorithms for the UET permutation flowshop problem with time delays. Comput. Oper. Res. 35, 525–537 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  18. 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)

    Article  Google Scholar 

  19. 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)

    Article  MATH  Google Scholar 

  20. 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)

    Article  MathSciNet  MATH  Google Scholar 

  21. Stafford, E.F., Tseng, F.T.: Two models for a family of flowshop sequencing problems. Eur. J. Oper. Res. 142, 282–293 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  22. Szwarc, W.: The flowshop problem with time lags and separated setup times. ZOR-Z. Oper. Res. 30, 15–22 (1986)

    MathSciNet  Google Scholar 

  23. Teghem, J., Pirlot, M.: Optimisation Approchée en Recherche Opérationnelle. Hermes Science Publications, Paris (2002)

    Google Scholar 

  24. Yang, D.L., Chern, M.S.: A two-machine flowshop sequencing problem with limited waiting time constraints. Comput. Ind. Eng. 28, 63–70 (1995)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Unité de recherche LOgistique Gestion Industrielle et de la Qualité (LOGIQ), Université de Sfax, Institut Supérieur de Gestion Industrielle de Sfax, Route el Mharza km 1.5, 3018, Sfax, Tunisie

    Emna Dhouib & Taïcir Loukil

  2. Service de Mathématique et de Recherche Opérationnelle (MathRO), Université de Mons /Faculté Polytechnique de Mons, 21, Place du Parc, 7000, Mons, Belgique

    Jacques Teghem

Authors
  1. Emna Dhouib
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jacques Teghem
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Taïcir Loukil
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Emna Dhouib.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dhouib, E., Teghem, J. & Loukil, T. Minimizing the Number of Tardy Jobs in a Permutation Flowshop Scheduling Problem with Setup Times and Time Lags Constraints. J Math Model Algor 12, 85–99 (2013). https://doi.org/10.1007/s10852-012-9180-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-012-9180-x

Keywords

Search

Navigation