Mathematical models for job shop scheduling problem with sequence-independent setup times
DOI:
https://doi.org/10.14488/1676-1901.v17i1.2504Keywords:
Scheduling. Job shop. Sequence-independent setup times. Mixed Integer Linear Programming.Abstract
This paper addresses the job shop scheduling problem with explicit and sequence-independent setup times to minimize the total time to complete the schedule (makespan). According to the well-known three-field notation, this problem is denoted by Jm|sjk|Cmax. In job shop production environment, a set of different machines or resources must process a set of jobs, where each job has a specific and predetermined route through the machines. For problems with two machines, this research proposes an adaptation of the classical Jackson’s Algorithm, which provides the optimal solution for the case with setup times included in the processing times of jobs. And for general problems with m machines, two mathematical models of mixed integer linear programming were designed and implemented to solve the two cases with anticipatory and non-anticipatory setup times. Anticipatory setup times can be started before the release of the job. The two models provide solutions to the problems in acceptable computational time for instances with up to 20 jobs and 7 machines.
Downloads
References
ADAMS, J.; BALAS, E.; ZAWACK, D. The shifting bottleneck procedure for job shop scheduling. Management Science, v. 34, p. 391-401, 1988. http://dx.doi.org/10.1287/mnsc.34.3.391
ALDAKHILALLAH, K.A.; RAMESH, R. Cyclic scheduling heuristic for a re-entrant job shop manufacturing environment. International Journal of Production Research, v. 39, p. 2635-2657, 2001. http://dx.doi.org/10.1080/00207540110047711
ALLAHVERDI, A. Third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, v. 246, n. 2, p. 345-378, 2015. http://dx.doi.org/10.1016/j.ejor.2015.04.004
ALLAHVERDI, A.; CHENG, T. C. E.; KOVALYOV, M. Y. A survey of scheduling problems with setups times or costs. European Journal of Operational Research, v. 187, n. 3, p. 985-1032, 2008. http://dx.doi.org/10.1016/j.ejor.2006.06.060
ALLAHVERDI, A.; GUPTA, J.N.D.; ALDOWAISAN, T. A review of scheduling research involving setup considerations. Omega – International Journal of Management Science, v. 27, p. 219-239, 1999. http://dx.doi.org/10.1016/S0305-0483(98)00042-5
ALLAHVERDI, A.; SOROUSH, H. M. The significance of reducing setup times/setup costs. European Journal of Operational Research, v. 187, n. 3, p. 978-984, 2008. http://dx.doi.org/10.1016/j.ejor.2006.09.010
AL-SALEM, A. A heuristic to minimize makespan in proportional parallel flow shops. International Journal of Computing & Information Sciences, v. 2, p. 98-107, 2004. http://www.ijcis.info/Vol2N2/98-107OKS.pdf
BLAZEWICZ, J.; DOMSCHKE, W., PESCH, E. The job shop scheduling problem: conventional and new solution techniques. European Journal of Operational Research, v. 93, p. 1-33, 1996.
http://dx.doi.org/10.1016/0377-2217(95)00362-2
CHAN, F. T. S.; CHOY K.L.; BIBHUSHAN. A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop. Expert Systems with Applications, v. 38, p. 8703-8715, 2011. http://dx.doi.org/10.1016/j.eswa.2011.01.078
CHIN, Y.L. Job shop scheduling heuristics for sequence dependent setup. Computers & Industrial Engineering, v. 29, p. 279-283, 1995. http://dx.doi.org/10.1016/0360-8352(95)00085-F
FREITAS, F.F.T.; VIEIRA, G.E. Tendências de aplicações da otimização por colônia de formigas na programação de job-shops. Revista Produção Online, v. 10, n. 1, p. 95-123, 2010. http://dx.doi.org/10.14488/1676-1901.v10i1.441
FUCHIGAMI, H. Y. Sequenciamento da produção em sistemas flow shop. UFG, Goiânia – GO, 2015.
JACKSON, J. R. An extension of Johnson’s results on job lot scheduling. Naval Research Logistics Quarterly, v. 3, p. 201-203, 1956. http://dx.doi.org/10.1002/nav.3800030307
JEONG, H.; PARK, J. LEACHMAN, R.C. A batch splitting method for a job shop scheduling problem in an MRP environment. International Journal of Production Research, v. 37, p. 3583-3598, 1999. http://dx.doi.org/10.1080/002075499190194
JOHNSON, S. M. Optimal two- and three- stage production schedules with setup times included. Naval Research Logistic Quarterly, v. 1, p. 61-68, 1954. http://dx.doi.org/10.1002/nav.3800010110
LOW, C.; HSU, C.-M., HUANG, K.-I. Benefits of lot splitting in job-shop scheduling. International Journal of Advanced Manufacturing Technology, v. 24, p. 773-780, 2004. http://dx.doi.org/10.1007/s00170-003-1785-9
MÜLLER, G. I.; GÓMEZ, A. T. Um estudo do comportamento dos tempos de makespan, atraso e setup no problema de escalonamento de job shop. Hifen, v. 31, n. 59-60, p. 148-154, 2007.
PACHECO, R.F.; SANTORO, M.C. Proposta de classificação hierarquizada dos modelos de solução para o problema de job shop scheduling. Gestão & Produção, v. 6, n. 1, p. 1-15, 1999. http://dx.doi.org/10.1590/S0104-530X1999000100001
PARVEEN, S.; ULLAH, H. Review on job-shop and flow-shop scheduling using multi criteria decision making. Journal of Mechanical Engineering, v. 41, n. 2, p. 130-146, 2010.
PINEDO, M. Scheduling: theory, algorithms, and systems. 5. ed. New Jersey: Prentice-Hall, 2015.
RAHIME, S.E.; ARSLAN, O. Simulation analysis of lot streaming in job shops with transportation queue disciplines. Simulation Modelling Practice and Theory, v. 17, p. 442-453, 2009.
http://dx.doi.org/10.1016/j.simpat.2008.10.002
SONG, H.; YI, S.; SHEN, H. A study of job shop standard setup time quota. Production Management, v. 10, n. 2, p. 185-196, 2016. http://dx.doi.org/10.1007/s11740-015-0649-0
SOTSKOV, Y.N.; TAUTENHAHN, T.; WERNER, F. On the application of insertion techniques for job shop problems with setup times. RAIRO – Operations Research, v. 33, n. 2, p. 209-245, 2010. http://dx.doi.org/10.1051/ro:1999110
TARANTILIS, C. D.; KIRANOUDIS, C. T. A list-based threshold accepting method for job shop scheduling problems. International Journal of Production Economics, v. 77, p. 159–171, 2002. http://dx.doi.org/10.1016/S0925-5273(01)00231-6
WILBRECHT, J.K.; PRESCOTT, W.B. The influence of setup time on job shop performance. Management Science, v. 16, p. B274-B280, 1969. http://dx.doi.org/10.1287/mnsc.16.4.B274
Published
How to Cite
Issue
Section
License
The Journal reserves the right to make spelling and grammatical changes, aiming to keep a default language, respecting, however, the style of the authors.
The published work is responsibility of the (s) author (s), while the Revista Produção Online is only responsible for the evaluation of the paper. The Revista Produção Online is not responsible for any violations of Law No. 9.610 / 1998, the Copyright Act.
The journal allows the authors to keep the copyright of accepted articles, without restrictions
This work is licensed under a Creative Commons License .
