Dinamik atölye tipi çizelgeleme problemine bir tavlama benzetimi yaklaşımı tabanlı simülasyon optimizasyonu

Abstract

Bu çalışmada, bir üretim çizelgeleme problem ele alınmaktadır. Bu çizelgeleme problemine atölye tipi bir üretim tipinde karşılaşılmaktadır. Üretim sistemi sürekli iş gelişlerinin söz konusu olduğu kesikli dinamik sistemdir. Çizelgeleme kurallarının birbirinden bağımsız şekilde kullanılmasının gerektiği makine bozulmaları ve değişen teslim süreleri gibi bazı durumların değerlendirilmesi için bir simülasyon modeli sunulmaktadır. En erken teslim süresi, en kısa işlem süresi ve ilk giren ilk çıkar kuralı olmak üzere üç çizelgeleme kuralı bu simülasyon modeline dahil edilmiştir. Dinamik sistemdeki belirsiz çizelgeleri ortaya koymak için tavlama benzetimi sezgiseli tabanlı bir simülasyon optimizasyonu yöntemi önerilmektedir. Sayısal analizlerde çizelgeleme kurallarının ve önerilen tavlama benzetimi sezgiselinin performansları simülasyon deneyleri kullanılarak kıyaslanmıştır.  Ortalama akış süresini ve ortalama gecikme süresini en küçükleyen amaç fonksiyonları farklı seviyelerdeki atölye kullanım oranı ve teslim süresi durumlarında incelenmiştir. Genel bir sonuç olarak, önerilen tavlama benzetimi sezgiselinin en erken teslim zamanı ve ilk giren ilk çıkar kurallarından daha iyi sonuç verdiği, en kısa işlem süresi kuralının en iyi sonuçları sağladığı gözlenmiştir. Fakat tavlama benzetimi sezgiseli en kısa işlem süresi kuralına çok yakın sonuçlara erişmektedir ve çözüm zamanının kritik olduğu uygulamalarda kabul edilebilir bir hesaplama yükü getirmektedir.

Keywords

• Atölye tipi çizelgeleme,Kesikli ve dinamik sistem,Tavlama benzetimi algoritması,Benzetim optimizasyonu,Çizelgeleme kuralları

A simulated annealing approach based simulation-optimisation to the dynamic job-shop scheduling problem

Abstract

In this study, we address a production scheduling problem. The scheduling problem is encountered in a job-shop production type. The production system is discrete and dynamic system in which jobs arrive continually. We introduce a simulation model (SM) to identify several situations such as machine failures, changing due dates in which scheduling rules (SRs) should be selected independently. Three SRs, i.e. the earliest due date rule (EDD), the shortest processing time first rule (SPT) and the first in first out rule (FIFO), are incorporated in a SM. A simulated annealing heuristic (SA) based simulation-optimisation approach is proposed to identify the unknown schedules in the dynamical system. In the numerical analysis, the performance of SRs and SA are compared using the simulation experiments. The objective functions minimising the mean flowtime and the mean tardiness are examined with varying levels of shop utilization and due date tightness. As an overall result, we observe that the proposed SA heuristic outperforms EDD and FIFO, the well-known SPT rule provides the best results. However, SA heuristic achieves very close results to the SPT and offers a reasonable computational burden in time-critical applications.

Keywords

• Job-shop scheduling,Discrete and dynamic system,Simulated annealing algorithm,Simulation-optimisation,Scheduling rules

References

1. Pinedo M. Scheduling Theory, Algorithms, and Systems. New York, USA, Springer-Verlag, 2015.
2. Baker KR. Elements of sequencing and scheduling, Hanover, USA, Dartmouth College, 1995.
3. Holthaus O, Rajendran C. “New scheduling rules for scheduling in a job shop-An experimental study”. The International Journal of Advanced Manufacturing Technology, 13(2), 148-153, 1997.
4. Sabuncuoğlu I, Bayız M. “Analysis of reactive scheduling problems in a job shop environment”. European Journal of Operational Research, 126(3), 567-586, 2000.
5. Alotaibia A, Lohsea N, Vub TM. “Dynamic agent-based bi-objective robustness for tardiness and energy in a dynamic flexible job shop”. CIRP Conference on Manufacturing Systems, Stuttgart, Germany, 25-27 May 2016.
6. Vinod V, Sridharan R. “Scheduling a dynamic job shop production system with sequence dependent setups: An experimental study”. Robotics and Computer Integrated Manufacturing, 24, 435-449, 2008.
7. Liu SQ, Ong HL, Ng KM. “Metaheuristics for minimizing the makespan of the dynamic shop scheduling problem”. Advances in Engineering Software, 36, 199-205, 2005.
8. Kundakcı N, Kulak O. “Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem.” Computers & Industrial Engineering, 96, 31-51, 2016.

9. Adibi MA, Zandieh M, Amiri M. “Multi-objective scheduling of dynamic job shop using variable neighborhood search”. Expert Systems with Applications, 37, 282-287, 2010.
10. Nie L, Gao L, Li P, Shao X. “Reactive scheduling in a job shop where jobs arrive over time”. Computers & Industrial Engineering, 66, 389-405, 2013.
11. Qiu X, Lau HYK. “An AIS-based hybrid algorithm with PDRs for multiobjective dynamic online job shop scheduling problem”. Applied Soft Computing, 13, 1340-1351, 2013.
12. Nguyen S, Zhang M, Johnston M, Tan KC. “Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming”. IEEE Transactions on Evolutionary Computation, 18(2), 193-208, 2014.
13. Fattahi P, Fallahi A. “Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability”. CIRP Journal of Manufacturing Science and Technology, 2, 114-123, 2010.
14. Rangsaritratsamee R, Ferrell W Jr, Kurz M. “Dynamic rescheduling that simultaneously considers efficiency and stability”. Computers & Industrial Engineering, 46, 1-15, 2004.
15. Nahavandi N, Zegordi S H, Abbasian M. “Solving the Dynamic Job Shop Scheduling Problem using Bottleneck and Intelligent Agents based on Genetic Algorithm”. International Journal of Engineering, 29(3), 347-358, 2016.
16. Aydemir E, Koruca HI. A new production scheduling module using priority-rule based genetic algorithm. International Journal of Simulation Modelling, 14(3), 450-462, 2015.
17. Ouelhadj D, Petrovic S. “A survey of dynamic scheduling in manufacturing systems”. Journal of scheduling, 12(4), 417-431, 2009.
18. Koruca, Hİ, Özdemir G, Aydemir, E, Çayırlı M. "Bir Simülasyon Yazılımı için Esnek İş Akış Planı Editörü Geliştirilmesi ve İşlemlerin Gantt Şemasında Çizelgelenmesi." Gazi Üniv. Müh. Mim. Fak. Der, 25(1), 77-81, 2010a.
19. Zülch G, Halil IK, Mikko B. "Simulation-supported change process for product customization–A case study in a garment company." Computers in Industry, 62(6), 568-577, 2011.
20. Koruca Hİ. "Simülasyon Destekli Vardiya Planlama Modülü Geliştirilmesi." Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 25(3), 369-382, 2010b.
21. Zülch G, Bogus T, Koruca HI, Kurbanoglu C, Brinkmeier B. "Simulation aided design of organizational structures in manufacturing systems using structuring strategies." Journal of Intelligent Manufacturing, 15(4), 431-437, 2004.
22. April J, Better M, Glover F, Kelly, J. “New advances and applications for marrying simulation and optimization”. IEEE Simulation Conference, Washington, USA, 5-8 December 2004.
23. Hamzadayı A, Yıldız G. “Hybrid strategy based complete rescheduling approaches for dynamic m identical parallel machines scheduling problem with a common server”. Simulation Modelling Practice and Theory, 63, 104-132, 2016.
24. Koruca, Hİ, Özdemir G, Aydemir, E, Çayırlı M. "The simulation-based performance measurement in an evaluation module for Faborg-Sim simulation software." Expert Systems with Applications, 37(12), 8211-8220, 2010c.
25. Chang FCR. “Heuristics for dynamic job shop scheduling with real-time updated queueing time estimates”. International Journal of Production Research, 35(3), 651-665, 1997.
26. Dominic PDD, Kaliyamoorthy S, Kumar S. “Efficient scheduling rules for dynamic job shop scheduling”. International Journal of Advanced Manufacturing Technology, 24, 70-75, 2004.
27. Gao Y, Ding YS, Zhang HY. “Job-shop scheduling considering rescheduling in uncertain dynamic environment”. International Conference On Management Science & Engineering, Moscow, Russia, 14-16 September 2009.
28. Ghomi SMTF, Iranpoor M. "Earliness-tardiness-lost sales dynamic job-shop scheduling.". Production Engineering, 4(2-3), 221-230, 2010.
29. Hao XC, Gen M. “Multi-objective job shop rescheduling by using evolutionary algorithm”. IEEJ Transactions on Electronics, Information and Systems, 131(3), 674-681, 2011.
30. Hao XC, Lin L. “Job shop rescheduling by using multi-objective genetic algorithm.” CIE40 International Conference on Computers and Industrial Engineering, Awaji Island, Japan, 26-28 July 2010.
31. Holloway CA, Nelson RT. “Job shop scheduling with due dates and variable processing times”. Management Science, 20(9), 1264-1275, 1974.
32. Holthaus O. “Scheduling in job shops with machine failures: an experimental study”. Computers & industrial engineering, 36(1), 137-162, 1999.
33. Hosseinabadi AAR, Siar H, Shamshirband S, Shojafar M, Nasir M HNM. “Using the gravitational emulation local search algorithm to solve the multi-objective flexible dynamic job shop scheduling problem in Small and Medium Enterprises”. Annals of Operations Research, 229, 451-474, 2015.
34. Kapanoglu M, Alikalfa M. “Learning IF-THEN priority rules for dynamic job shops using genetic algorithms”. Robotics and Computer-Integrated Manufacturing, 27, 47-55, 2011.
35. Kutanoğlu E, Sabuncuoğlu I. “Routing-based reactive scheduling policies for machine failures in dynamic job shops”. International Journal of Production Research, 39(14), 3141-3158, 2001.
36. Li Y, Chen Y. “Neural network and genetic algorithm-based hybrid approach to dynamic job shop scheduling problem.” IEEE international Conference on Systems, Man, and Cybernetic, San Antonio, TX, USA, 11-14 October 2009.
37. Lu MS, Romanowski R. “Multicontextual scheduling rules for job shops with dynamic job arrival”. International Journal of Advanced Manufacturing Technology, 67, 19-33, 2013.
38. Muhlemann AP, Lockett AG, Farn CK. “Job shop scheduling heuristics and frequency of scheduling”. International Journal of Production Research, 20(2), 227-241, 1982.
39. Nelson RT, Holloway CA, Wong RM. “Centralized scheduling and priority implementation heuristics for a dynamic job shop model”. AIIE Transactions, 9(1), 95-102, 1977.
40. Rajendran C, Holthaus O. “A comparative study of scheduling rules in dynamic flowshops and jobshops”. European Journal of Operational Research, 116, 156-170, 1999.
41. Sharma P, Jain A. “Analysis of scheduling rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times”. Frontiers of Mechanical Engineering, 9(4), 380-389, 2014.
42. Sharma P, Jain A. “Performance analysis of scheduling rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times: Simulation approach”. CIRP Journal of Manufacturing Science and Technology, 10, 110-119, 2015.
43. Suwa H, Sandoh H. “Capability of cumulative delay based reactive scheduling for job shops with machine failures”. Computers & Industrial Engineering, 53, 63-78, 2007.
44. Qi JG, Burns GR, Harrison DK. “The application of parallel multipopulation genetic algorithms to dynamic job-shop scheduling”. International Journal of Advanced Manufacturing Technology, 16, 609-615, 2000.
45. Xiong H, Fan H, Jiang G, Li G. “A simulation-based study of scheduling rules in a dynamic job shop scheduling problem with batch release and extended technical precedence constraints”. European Journal of Operational Research, 257, 13-24, 2017.
46. Zhang L, Gao L, Li X. “A hybrid genetic algorithm and tabu search for multi-objective dynamic job shop scheduling problem”. International Journal of Production Research, 51(12), 3516-3531, 2013.
47. Ze T, Lie-Yang X, Chang-Zhong H, Xiao-Xia L. "Petri Net and GASA Based Approach for Dynamic JSSP". International Journal of Performability Engineering, 3(2), 213-224, 2007.
48. Baker KR. “Sequencing rules and due-date assignments in a job shop”. Management Science, 30(9), 1093-1104, 1984.
49. Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E. “Equation of state calculations by fast computing machines”. The journal of chemical physics, 21(6), 1087-1092, 1953.
50. Kirkpatrick S, Gelatt CD, Vecchi MP. “Optimisation by simulated annealing”. Science, 220(4598), 671-680, 1983.
51. Law AM, Kelton WD, Kelton WD. Simulation modeling and analysis. 3rd ed. New York, USA, McGraw-Hill, 1991.