[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Mixed Integer Programming Formulations for Two-Machine Flow Shop Scheduling with an Availability Constraint

  • Research Article - Computer Engineering and Computer Science
  • Published:
Arabian Journal for Science and Engineering Aims and scope Submit manuscript

Abstract

A two-machine flow shop scheduling scenario with an availability constraint on one of the two machines is considered. Seven mixed integer programming formulations (MIPFs) are proposed for the problem where the availability constraint is imposed on the first machine. Seven analogs are proposed for its counterpart. Size complexity analysis of these MIPFs is provided. Numerical results indicate that, for either one of the two problems, each of the corresponding first three MIPFs can solve instances of size up to 100 jobs in reasonable times.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Lee, C.-L.: Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint. Oper. Res. Lett. 20(3), 129–139 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  2. Lee, C.-Y.: Two-machine flowshop scheduling with availability constraints. Eur. J. Oper. Res. 114(2), 420–429 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  3. Kubzin, M.A.; Potts, C.N.; Strusevich, V.A.: Approximation results for flow shop scheduling problems with machine availability constraints. Comput. Oper. Res. 36, 379–390 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Hadda, H.; Dridi, N.; Hajri-Gabouj, S.: An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs. 4OR 8, 87–99 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Hnaien, F.; Yalaoui, F.; Mhadhbi, A.: Makespan minimization on a two-machine flowshop with an availability constraint on the first machine. Int. J. Prod. Econ. 164, 95–104 (2015)

    Article  Google Scholar 

  6. Cheng, T.C.E.; Wang, G.: Two-machine flowshop scheduling with consecutive availability constraints. Inf. Process. Lett. 71(2), 49–54 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cheng, T.C.E.; Wang, G.: An improved heuristic for two-machine flowshop scheduling with an availability constraint. Oper. Res. Lett. 26(5), 223–229 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  8. Ng, C.; Kovalyov, M.Y.: An FPTAS for scheduling a two-machine flowshop with one unavailability interval. Nav. Res. Logist. 51, 307–315 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  9. Breit, J.: An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint. Inf. Process. Lett. 90, 273–278 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  10. Blazewicz, J.; Dror, M.; Weglarz, J.: Mathematical programming formulations for machine scheduling: a survey. Eur. J. Oper. Res. 51(3), 283–300 (1991)

    Article  MATH  Google Scholar 

  11. Keha, A.B.; Khowala, K.; Fowler, J.W.: Mixed integer programming formulations for single machine scheduling problems. Comput. Ind. Eng. 56(1), 357–367 (2009)

    Article  Google Scholar 

  12. Baker, K.R.; Brian, K.: Solving the single-machine sequencing problem using integer programming. Comput. Ind. Eng. 59(4), 730–735 (2010)

    Article  Google Scholar 

  13. Della Croce, F.: MP or not MP: that is the question. J. Sched. 19, 33–42 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  14. Yin, Y.; Wang, Y.; Cheng, T.C.E.; Wang, D.-J.; Wu, C.-C.: Two-agent single-machine scheduling to minimize the batch delivery cost. Comput. Ind Eng. 92, 16–30 (2016)

    Article  Google Scholar 

  15. Pinedo, M.: Scheduling: Theory, Algorithms and Systems, 5th edn. Springer, New York (2015)

    MATH  Google Scholar 

  16. Tseng, F.T.; Stafford, E.F.; Gupta, J.N.D.: An empirical analysis of integer programming formulations for the permutation flowshop. Omega 32(4), 285–293 (2004)

    Article  Google Scholar 

  17. Stafford, E.F.; Tseng, F.T.; Gupta, J.N.D.: Comparative evaluation of MILP flowshop models. J. Oper. Res. Soc. 56(1), 88–101 (2005)

    Article  MATH  Google Scholar 

  18. Chen, J.-S.: Optimization models for the machine scheduling problem with a single flexible maintenance activity. Eng. Optim. 38(1), 53–71 (2006)

    Article  MathSciNet  Google Scholar 

  19. Chen, J.-S.: Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan. Eur. J. Oper. Res. 190(1), 90–102 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  20. Chen, J.-S.: Optimization models for the tool change scheduling problem. Omega 36(5), 888–894 (2008)

    Article  Google Scholar 

  21. Xu, D.; Liu, A.; Yang, D.-L.: Mathematical programming models for competitive two-agent single-machine scheduling with flexible periodic maintenance activities. Arab. J. Sci. Eng. 39(5), 3715–3722 (2014)

    Article  MathSciNet  Google Scholar 

  22. Wagner, H.M.: An integer linear-programming model for machine scheduling. Nav. Res. Logist. Q. 6(2), 131–140 (1959)

    Article  MathSciNet  Google Scholar 

  23. Stafford, E.F.: On the development of a mixed-integer linear programming model for the flowshop sequencing problem. J. Oper. Res. Soc. 39(12), 1163–1174 (1988)

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  25. Stafford, E.F.; Tseng, F.T.: On “redundant” constraints in Stafford’s MILP model for the flowshop problem. J. Oper. Res. Soc. 54(10), 1102–1105 (2003)

    Article  MATH  Google Scholar 

  26. Ronconi, D.P.; Birgin, E.G.: Mixed-integer programming models for flowshop scheduling problems minimizing the total earliness and tardiness. In: Ríos-Mercado, R.Z., Ríos-Solís, Y.A. (eds.) Just-in-Time Systems, pp. 91–105. Springer, New York (2012)

    Chapter  Google Scholar 

  27. Tseng, F.T.; Stafford, E.F.: New MILP models for the permutation flowshop problem. J. Oper. Res. Soc. 59(10), 1373–1386 (2008)

    Article  MATH  Google Scholar 

  28. Wilson, J.M.: Alternative formulations of a flow-shop scheduling problem. J. Oper. Res. Soc. 40(4), 395–399 (1989)

    Article  MATH  Google Scholar 

  29. Tseng, F.T.; Stafford, E.F.: Two MILP models for the \(N\times M\) SDST flowshop sequencing problem. Int. J. Prod. Res. 39(8), 1777–1809 (2001)

    Article  MATH  Google Scholar 

  30. Manne, A.S.: On the job-shop scheduling problem. Oper. Res. 8(2), 219–223 (1960)

    Article  MathSciNet  Google Scholar 

  31. Liao, C.-J.; You, C.-T.: An improved formulation for the job-shop scheduling problem. J. Oper. Res. Soc. 43(11), 1047–1054 (1992)

    Article  MATH  Google Scholar 

  32. Pan, C.-H.: A study of integer programming formulations for scheduling problems. Int. J. Syst. Sci. 28(1), 33–41 (1997)

    Article  MATH  Google Scholar 

  33. Xu, D.; Cheng, Z.; Yin, Y.; Li, H.: Makespan minimization for two parallel machines scheduling with a periodic availability constraint. Comput. Oper. Res. 36(6), 1809–1812 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  34. Liu, M.; Zheng, F.; Chu, C.; Xu, Y.: Optimal algorithms for online scheduling on parallel machines to minimize the makespan with a periodic availability constraint. Theor. Comput. Sci. 412(39), 5225–5231 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  35. Li, G.; Lu, X.: Two-machine scheduling with periodic availability constraints to minimize makespan. J. Ind. Manag. Optim. 11(2), 685–700 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  36. Xu, D.; Sun, K.; Li, H.: Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan. Comput. Oper. Res. 35(4), 1344–1349 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  37. Akturk, M.S.; Ghosh, J.B.; Gunes, E.D.: Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance. Nav. Res Logist. 50(1), 15–30 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  38. Akturk, M.S.; Ghosh, J.B.; Gunes, E.D.: Scheduling with tool changes to minimize total completion time: basic results and SPT performance. Eur. J. Oper. Res. 157(3), 784–790 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  39. Akturk, M.S.; Ghosh, J.B.; Kayan, R.K.: Scheduling with tool changes to minimize total completion time under controllable machining conditions. Comput. Oper. Res. 34(7), 2130–2146 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  40. Xu, D.; Liu, M.; Yin, Y.; Hao, J.: Scheduling tool changes and special jobs on a single machine to minimize makespan. Omega 41(2), 299–304 (2013)

    Article  Google Scholar 

  41. Al-Dhaheri, N.; Diabat, A.: The quay crane scheduling problem. J. Manuf. Syst. 36, 87–94 (2015)

    Article  MATH  Google Scholar 

  42. Al-Dhaheri, N.; Jebali, A.; Diabat, A.: A simulation-based genetic algorithm approach for the quay crane scheduling under uncertainty. Simul. Model. Pract. Theory 66, 122–138 (2016)

    Article  Google Scholar 

  43. Al-Dhaheri, N.; Jebali, A.; Diabat, A.: The quay crane scheduling problem with nonzero crane repositioning time and vessel stability constraints. Comput. Ind. Eng. 94, 230–244 (2016)

    Article  Google Scholar 

  44. Al-Dhaheri, N.; Diabat, A.: A Lagrangian relaxation-based heuristic for the multi-ship quay crane scheduling problem with ship stability constraints. Ann. Oper. Res. 248, 1–24 (2017)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Tongji University, Shanghai, 200092, People’s Republic of China

    Zhijun Xu

  2. School of Science, East China University of Technology, Nanchang, 330013, Jiangxi, People’s Republic of China

    Zhijun Xu, Dehua Xu, Jie He, Qi Wang, Aihua Liu & Junfang Xiao

Authors
  1. Zhijun Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dehua Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jie He
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Qi Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Aihua Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Junfang Xiao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhijun Xu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, Z., Xu, D., He, J. et al. Mixed Integer Programming Formulations for Two-Machine Flow Shop Scheduling with an Availability Constraint. Arab J Sci Eng 43, 777–788 (2018). https://doi.org/10.1007/s13369-017-2763-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13369-017-2763-0

Keywords

Search

Navigation