A Mathematical Model for Stochastic Unrelated Parallel Machine Scheduling Problem

Abstract

If a job can be processed by any machines that can do the same operation, these machines are called parallel machines. If parallel machines have different processing times for a job, these machines are unrelated. The unrelated parallel machine scheduling problem (UPM) has an important place in the scheduling literature because it has a wide application area in the industry, and it is a sub-problem of more complex problems such as flexible job-shop scheduling problem. It is difficult to precisely determine the values of the parameters of the problem, such as processing times, setup times, due dates. These parameters may vary depending on many factors, such as changes in demands and due dates by the customer at the last moment, machine malfunctions, and disruptions in raw material supply. For this reason, UPM has a stochastic structure by nature, and there are many studies in the literature that deal with the problem as deterministic, as well as studies that deal with it as stochastic. However, most of the studies dealing with the problem as stochastic have examined the case of stochastic processing times. In this study, unlike the general literature, the contribution of handling the sequence-dependent setup times as stochastic was investigated. A two-stage stochastic programming approach is used for stochastic UPM with sequence-dependent setup time. A mathematical model is proposed for the stochastic problem. The effectiveness of the proposed model is demonstrated on randomly generated test problems. First of all, all test problems were solved with a deterministic model, assuming that the parameters were deterministic, and schedules were obtained. Then, the sequence-dependent setup times were handled stochastic, and the problems were solved with the proposed stochastic model. Finally, the contribution of stochastic handling of the sequence-dependent setup time for each problem is calculated. Tests have revealed that even for small-sized problems with only 10 jobs, treating the problem as stochastic shortens the completion time of the last job by an average of 0.305%.

Keywords

• Unrelated parallel machine scheduling problem
• Two-stage stochastic programming
• stochastic sequence-dependent setup times.

Stokastik İlişkisiz Paralel Makine Çizelgeleme Problemi için bir Matematiksel Model

Öz

Bir iş, aynı işlemi yapabilen makinaların herhangi birisinde işlem görebiliyor ise bu makinalar, paralel makinalar olarak adlandırılmaktadır. Eğer paralel makinaların bir iş için işlem süreleri farklılık gösteriyorsa bu makinalar ilişkisizdir. İlişkisiz paralel makine çizelgeleme problemi (UPM) hem endüstride yaygın bir uygulama alanına sahip olması hemde esnek atölye tipi çizelgeleme problemi gibi daha karmaşık problemlerin alt problemi olması nedeniyle çizelgeleme literatüründe önemli bir yere sahiptir. Problemin işlem süreleri, hazırlık süreleri, müşteri terminleri gibi parametrelerinin değerlerini kesin olarak belirlemek zordur. Bu parametreler taleplerin ve termin tarihlerinin müşteri tarafından son anda değiştirilmesi, makine arızaları, hammadde temininde aksamalar gibi pek çok faktöre bağlı olarak değişkenlik gösterebilmektedir. UPM doğası gereği stokastik bir yapıya sahiptir ve nedenle literatürde problemi deterministik olarak ele alan çok sayıda çalışmanın yanısıra stokastik olarak ele alan çalışmalar da mevcuttur. Ancak problemi stokastik olarak ele alan çalışmaların çoğu işlem sürelerinin stokastik olması durumunu incelemişlerdir. Bu çalışmada ise literatürün genelinden farklı olarak sıra bağımlı hazırlık sürelerini stokastik olarak ele almanın katkısı araştırılmıştır. Sıra bağımlı hazırlık süreli stokastik UPM için iki aşamalı stokastik programlama yaklaşımı kullanılmıştır. Stokastik problem için bir matematiksel model önerilmiştir. Önerilen modelin etkinliği rassal türetilen test problemleri üzerinde gösterilmiştir. Öncelikle tüm test problemleri parametrelerin deterministik olduğu varsayımı ile deterministik model ile çözülmüş ve çizelgeler elde edilmiştir. Daha sonra sıra bağımlı hazırlık süreleri stokastik olarak ele alınmış ve problemler önerilen stokastik model ile çözülmüştür. Son olarak her bir problem için sıra bağımlı hazırlık süresini stokastik ele almanın katkısı hesaplanmıştır. Yapılan testler, sadece 10 işin olduğu küçük boyutlu problemler için bile problemi stokastik olarak ele almanın son işin tamamlanma zamanını ortalama yüzde %0,305 kısalttığını ortaya koymuştur.

Anahtar Kelimeler

• İlişkisiz parallel makina çizelgeleme problemi
• İki aşamalı stokastik programlama
• stokastik sıra bağımlı hazırlık süreleri

References

1. Allahverdi, A. 2008. “Three-machine flowshop scheduling problem to minimize makespan with bounded setup and processing times.” Journal of the Chinese Institute of Industrial Engineers 25(1): 52–61.
2. Allahverdi, A. 2009. “Three-machine flowshop scheduling problem to minimize maximum lateness with bounded setup and processing times.” Journal of Operations and Logistics 2: 1-11.
3. Allahverdi, A. 2015. “The third comprehensive survey on scheduling problems with setup times/costs.” European Journal of Operational Research 246: 345-378.
4. Atakan, S. , K. Bülbül • and N. Noyan. 2017. “Minimizing value-at-risk in single-machine scheduling” Ann Oper Res 248:25–73.
5. Aydilek, A., H. Aydilek, and A. Allahverdi. 2013. “Increasing the profitability and competitiveness in a production environment with random and bounded setup times. “International Journal of Production Research 51: 106–117.
6. Aydilek, H., A. Aydilek, and A. Allahverdi. 2015. “Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan.” International Journal of Production Research 53: 2803–2819.
7. Aydilek, H.,and A. Allahverdi. 2013. “A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times.” Applied Mathematical Modelling 37 (12-13): 7164–7173.
8. Baker, K.R., 2014, “Minimizing earliness and tardiness costs in stochastic scheduling”, European Journal of Operational Research, 236, 445–452.

9. Chang, Z., S. Song , Y. Zhang , J.Y. Ding, R. Zhang, and R. Chiong. 2017. “Distributionally robust single machine scheduling with risk aversion.” European Journal of Operational Research 256: 261–274.
10. Ertem M., Ozcelik F., Sarac T. (2019), “Single machine scheduling problem with stochastic sequence-dependent setup times”, International Journal of Production Research, DOI:10.1080/00207543.2019.1581383.
11. Gu, J., M. Gu, and X. Gu. 2014. “Optimal Rules for Single Machine Scheduling with Stochastic Breakdowns.” Mathematical Problems in Engineering 1-9.
12. Gu, M. and Lu, X., 2010, “Stochastic scheduling problem with varying weight for each job”, ASIA-PACIFIC JOURNAL OF CHEMICAL ENGINEERING, 5, 681–689.
13. Iranpoor, M., Fatemi Ghomi, S.M.T., Zandieh, M., 2013, “Due-date assignment and machine scheduling in a low machine-rate situation with stochastic processing times” Computers & OperationsResearch, 40, 1100–1108.
14. Lemos, R.F., Ronconi, D.P. 2015. “Heuristics for the stochastic single-machine problem with E/T costs”. International Journal of Production Economics 168:131–142.
15. Rajendran, C., & Ziegler, H. 2003. “Scheduling to minimize the sum of weighted flowtime and weighted tardiness of jobs in a flowshop with sequence-dependent setup times.” European Journal of Operational Research, 149(3), 513-522.
16. Ronconi, D.P., and W.B. Powell. 2010. “Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming.” Journal of Scheduling 13: 597–607.
17. Salmasnia, A., M. Khatami, R.B. Kazemzadeh, S.H. Zegordi. 2015. “Bi-objective single machine scheduling problem with stochastic processing times.” TOP, 23:275–297.
18. Sharma,P., and A. Jain. 2014. “Analysis of dispatching rules in a stochastic dynamic jobshop manufacturing system with sequence-dependent setup times.” Frontiers of Mechanical Engineering 9(4): 380–389.
19. Soroush, H.M. 2010. “Solving a stochastic single machine problem with initial idle time and quadratic objective.” Computers & Operations Research 37: 1328–1347.
20. Van den Akker, M., and H. Hoogeveen. 2008. “Minimizing the number of late jobs in a stochastic setting using a chance constraint.” Journal of Scheduling 11: 59–69.
21. Wang, D.J., Liu, F., Wang, Y.Z. and Jin, Y., 2015. “A knowledge-based evolutionary proactive scheduling approach in the presence of machine breakdown and deterioration effect.” Knowledge-Based Systems, 90, pp.70-80.
22. Xu, L., Wang, Q. and Huang, S., 2015. “Dynamic order acceptance and scheduling problem with sequence-dependent setup time.” International Journal of Production Research, 53(19), pp.5797-5808.
23. Zhang L., Y. Lin, Y. Xiao and X. Zhang. 2018. “Stochastic single-machine scheduling with random resource arrival times.” International Journal of Machine Learning and Cybernetics 9(7): 1101–1107.
24. Zhang, J., Yang, W., Tu, Y. 2013, “Scheduling with compressible and stochastic release dates”, Computers &OperationsResearch, 40, 1758–1765.