Stokastik Teslim Zamanlı Tek Makine Çizelgeleme Problemi İçin Bir Harmoni Arama Algoritması

Abstract

Bir iş, teslim zamanından sonra tamamlandıysa o iş gecikir. İşlerin gecikmesinin, müşteri memnuniyetsizliği ve müşterilere ödenecek cezalar gibi ağır bedelleri olabileceğinden önlenmesi önemlidir. Eğer teslim zamanlarında bir belirsizlik var ise bir başka değişle müşterilerin ürünleri talep ettikleri tarihi öne çekmeleri ya da ertelemeleri mümkün ise bu durumda işler çizelgelenirken mutlaka bu belirsizliğin göz önünde bulundurulması gerekir. Bu nedenle bu çalışmada, stokastik teslim zamanlı tek makine çizelgeleme problemi ele alınmıştır. Ele alınan problemin çözümü için iki aşamalı bir stokastik programlama modeli önerilmiştir. Ancak problemin NP-zor doğası, büyük boyutlu problemlerin kesin çözüm yaklaşımları ile çözülebilmesine engeldir. Bu nedenle büyük boyutlu problemlerin çözülebilmesi için de bir harmoni arama algoritması önerilmiştir. Önerilen çözüm yaklaşımlarının performansları rassal türetilen test problemleri kullanılarak gösterilmiştir. Elde edilen test sonuçları, teslim zamanlarının stokastik doğasının dikkate alınmasının toplam gecikmeyi %10’a kadar azaltabileceğini ortaya koymuştur.

Keywords

• Tek makine çizelgeleme problemi
• Stokastik teslim zamanı
• Harmoni arama algoritması
• Stokastik programlama

A Harmony Search Algorithm for The Single Machine Scheduling Problem with Stochastic Due Dates

Abstract

If a job is completed after its due date, that job is tardy. It is important to avoid tardiness as it can have heavy costs such as customer dissatisfaction and customer penalties. If there is any uncertainty in the due dates, in other words, if it is possible to change due dates as earlier or later, then this uncertainty must be taken into account when scheduling the jobs. Therefore, in this study, the single machine scheduling problem with stochastic due dates is considered. A two-stage stochastic programming method is proposed for the solution of the considered problem. However, the NP-hard nature of the problem prevents finding a feasible solution for large-scale problems with exact solution approaches. Therefore, a harmony search algorithm is proposed for solving large-size problems. The performances of the proposed solution approaches are demonstrated using randomly generated test problems. The test results revealed that taking into account the stochastic nature of due dates can reduce the total tardiness by up to 10%.

Keywords

• Single machine scheduling problem
• Stochastic due dates
• Harmony search algorithm
• Stochastic programming

References

1. [1] Jang, W., Klein, C.M., 2002. Minimizing the expected number of tardy jobs when processing times are normally distributed. Operations Research Letters, Vol.30, pp.100–106. DOI: https://doi.org/10.1016/S0167-6377(02)00110-4.
2. [2] Seo, D.K., Klein, C.M., Jang, W., 2005. Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models. Computers & Industrial Engineering, Vol.48, pp.153–161. DOI: https://doi.org/10.1016/j.cie.2005.01.002.
3. [3] Van den Akker, M., Hoogeveen, H., 2008. Minimizing the number of late jobs in a stochastic setting using a chance constraint. Journal of Scheduling, Vol.11, pp.59–69. DOI: https://doi.org/10.1007/s10951-007-0034-8.
4. [4] Elyasi, A., Salmasi, N., 2013. Stochastic scheduling with minimizing the number of tardy jobs using chance constrained programming. Mathematical and Computer Modelling, Vol.57, pp.1154–1164. DOI: https://doi.org/10.1016/j.mcm.2012.10.017.
5. [5] Elyasi, A., Salmasi, N., 2013. Due date assignment in single machine with stochastic processing times. International Journal of Production Research, Vol.51(8), pp.2352–2362. DOI: https://doi.org/10.1080/00207543.2012.737945.
6. [6] Soroush, H.M., 2007. Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem. European Journal of Operational Research, Vol.181, pp.266–287. DOI: https://doi.org/10.1016/j.ejor.2006.05.036.
7. [7] Soroush, H.M., 2010. Solving a stochastic single machine problem with initial idle time and quadratic objective. Computers & Operations Research, Vol.37, pp.1328–1347. DOI: https://doi.org/10.1016/j.cor.2009.10.002.
8. [8] Salmasnia, A., Khatami, M., Kazemzadeh, R.B., Zegordi, S.H., 2015. Bi-objective single machine scheduling problem with stochastic processing times. TOP, Vol.23, pp.275–297. DOI: https://doi.org/10.1007/s11750-014-0337-9.

9. [9] Chang, Z., Song, S., Zhang, Y., Ding, J.Y., Zhang, R., Chiong, R., 2017. Distributionally robust single machine scheduling with risk aversion. European Journal of Operational Research, Vol.256, pp.261–274. DOI: https://doi.org/10.1016/j.ejor.2016.06.025.
10. [10] Atakan, S., Bülbül, K., Noyan, N., 2017. Minimizing value-at-risk in single-machine scheduling. Annals of Operations Research, Vol.248, pp.25–73. DOI: https://doi.org/10.1007/s10479-016-2251-z.
11. [11] Lemos, R.F., Ronconi, D.P., 2015. Heuristics for the stochastic single-machine problem with E/T costs. International Journal of Production Economics, Vol.168, pp.131–142. DOI: https://doi.org/10.1016/j.ijpe.2015.06.014.
12. [12] 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 & Operations Research, Vol.40, pp.1100–1108. DOI: https://doi.org/10.1016/j.cor.2012.11.013.
13. [13] Baker, K.R., 2014. Minimizing earliness and tardiness costs in stochastic scheduling. European Journal of Operational Research, Vol.236, pp.445–452. DOI: https://doi.org/10.1016/j.ejor.2013.12.011.
14. [14] Qi, X.D., Yin, G., Birge, J.R., 2000. Scheduling problems with random processing times under expected earliness/tardiness costs. Stochastic Analysis and Applications, Vol.18(3), pp.453–473. DOI: https://doi.org/10.1080/07362990008809680.
15. [15] Qi, X.D., Yin, G., Birge, J.R., 2000. Single-machine scheduling with random machine breakdowns and randomly compressible processing times. Stochastic Analysis and Applications, Vol.18(4), pp.635–653. DOI: https://doi.org/10.1080/07362990008809689.
16. [16] Wang, D.J., Liu, F., Wang, Y.Z., Jin, Y., 2015. A knowledge-based evolutionary proactive scheduling approach in the presence of machine breakdown and deterioration effect. Knowledge-Based Systems, Vol.90, pp.70–80. DOI: https://doi.org/10.1016/j.knosys.2015.09.032.
17. [17] Lu, C.C., Lin, S.W., Ying, K.C., 2012. Robust scheduling on a single machine to minimize total flow time. Computers & Operations Research, Vol.39, pp.1682–1691. DOI: https://doi.org/10.1016/j.cor.2011.10.003.
18. [18] Zhang, L., Lin, Y., Xiao, Y., Zhang, X., 2018. Stochastic single-machine scheduling with random resource arrival times. International Journal of Machine Learning and Cybernetics, Vol.9(7), pp.1101–1107. DOI: https://doi.org/10.1007/s13042-016-0631-y.
19. [19] Cai, X., Wang, L., Zhou, X., 2007. Single-machine scheduling to stochastically minimize maximum lateness. Journal of Scheduling, Vol.10, pp.293–301. DOI: https://doi.org/10.1007/s10951-007-0026-8.
20. [20] Jia, C., 2001. Stochastic single machine scheduling with an exponentially distributed due date. Operations Research Letters, Vol.28, pp.199–203. DOI: https://doi.org/10.1016/S0167-6377(01)00065-7.
21. [21] Benmansour, R., Allaoui, H., Artiba, A., 2012. Stochastic single machine scheduling with random common due date. International Journal of Production Research, Vol.50(13), pp.3560–3571. DOI: https://doi.org/10.1080/00207543.2012.671589.
22. [22] Cai, X., Zhou, X., 2005. Single-machine scheduling with exponential processing times and general stochastic cost functions. Journal of Global Optimization, Vol.31, pp.317–332. DOI: https://doi.org/10.1007/s10898-004-5702-z.
23. [23] Cai, X., Zhou, X., 2000. Asymmetric earliness and tardiness scheduling with exponential processing times on an unreliable machine. Annals of Operations Research, Vol.98(1–4), pp.313–331. DOI: https://doi.org/10.1023/A:1019220826984.
24. [24] Cai, X., Zhou, X., 2006. Stochastic scheduling with asymmetric earliness and tardiness penalties under random machine breakdowns. Probability in the Engineering and Informational Sciences, Vol.20, pp.635–654. DOI: https://doi.org/10.1017/S0269964806060396.
25. [25] Cai, X., Wu, X., Zhou, X., 2007. Single-machine scheduling with general costs under compound-type distributions. Journal of Scheduling, Vol.10(1), pp.77–84. DOI: https://doi.org/10.1007/s10951-006-0327-3.
26. [26] Zhang, J., Yang, W., Tu, Y., 2013. Scheduling with compressible and stochastic release dates. Computers & Operations Research, Vol.40, pp.1758–1765. DOI: https://doi.org/10.1016/j.cor.2013.01.011.
27. [27] Ronconi, D.P., Powell, W.B., 2010. Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming. Journal of Scheduling, Vol.13, pp.597–607. DOI: https://doi.org/10.1007/s10951-009-0160-6.
28. [28] Xu, L., Wang, Q., Huang, S., 2015. Dynamic order acceptance and scheduling problem with sequence-dependent setup time. International Journal of Production Research, Vol.53(19), pp.5797–5808. DOI: https://doi.org/10.1080/00207543.2015.1005768.
29. [29] Ertem, M., Ozcelik, F., Saraç, T., 2019. Single machine scheduling problem with stochastic sequence-dependent setup times. International Journal of Production Research, Vol.57(10), pp.3273–3289. DOI: https://doi.org/10.1080/00207543.2019.1581383.
30. [30] Ozcelik, F., Ertem, M., Saraç, T., 2022. A stochastic approach for the single-machine scheduling problem to minimize total expected cost with client-dependent tardiness costs. Engineering Optimization, Vol.54(7), pp.1178–1192. DOI: https://doi.org/10.1080/0305215X.2021.1919098.
31. [31] Roohnavazfar, M., Manerba, D., Fotio Tiotsop, L., Reza Pasandideh, S.H., Tadei, R., 2021. Stochastic single machine scheduling problem as a multi-stage dynamic random decision process. Computational Management Science, Vol.18, pp.267–297. DOI: https://doi.org/10.1007/s10287-020-00386-1.
32. [32] Gu, J., Gu, M., Gu, X., 2014. Optimal rules for single machine scheduling with stochastic breakdowns. Mathematical Problems in Engineering, Vol.2014, Article ID: 260415. DOI: https://doi.org/10.1155/2014/260415.
33. [33] Yue, F., Song, S.J., Jia, P., Wu, G.P., Zhao, H., 2020. Robust single machine scheduling problem with uncertain job due dates for industrial mass production. Journal of Systems Engineering and Electronics, Vol.31(2), pp.350–358. DOI: https://doi.org/10.23919/JSEE.2020.000012.
34. [34] Wei, W., 2019. Single machine scheduling with stochastically dependent times. Journal of Scheduling, Vol.22, pp.677–689. DOI: https://doi.org/10.1007/s10951-019-00600-2.
35. [35] Geem, Z.W., Kim, J.H., Loganathan, G.V., 2001. A new heuristic optimization algorithm: Harmony search. Simulation, Vol.76(2), pp.60–68. DOI: https://doi.org/10.1177/003754970107600201.
36. [36] Zammori, F., Braglia, M., Castellano, D., 2014. Harmony search algorithm for single-machine scheduling problem with planned maintenance. Computers & Industrial Engineering, Vol.76, pp.333–346. DOI: https://doi.org/10.1016/j.cie.2014.08.001.
37. [37] Gao, K.Z., Suganthan, P.N., Pan, Q.K., Taşgetiren, M.F., 2015. An effective discrete harmony search algorithm for flexible job shop scheduling problem with fuzzy processing time. International Journal of Production Research, Vol.53, pp.5896–5911. DOI: https://doi.org/10.1080/00207543.2015.1020174.
38. [38] Saraç, T., Tutumlu, B., 2022. A bi-objective mathematical model for an unrelated parallel machine scheduling problem with job-splitting. Journal of the Faculty of Engineering and Architecture of Gazi University, Vol.37(4), pp.2293–2308. DOI: https://doi.org/10.17341/gazimmfd.967343.
39. [39] Saraç, T., Tutumlu, B., 2022. A mixed-integer programming model and solution approach to determine the optimum machine number in the unrelated parallel machine scheduling problem. Journal of the Faculty of Engineering and Architecture of Gazi University, Vol.37(1), pp.329–345. DOI: https://doi.org/10.17341/gazimmfd.686683.
40. [40] Logendran, R., McDonell, B., Smucker, B., 2006. Scheduling unrelated parallel machines with sequence-dependent setups. Applied Mathematics and Computation, Vol.181(2), pp.1008–1017. DOI: https://doi.org/10.1016/j.amc.2006.02.048.