Seru Scheduling Problems with Multiple Due-Windows Assignment and Learning Effect

Abstract

This paper deals with seru scheduling problems with multiple due windows assignment and DeJong’s learning effect. Specific time intervals are assigned to jobs with multiple due windows and learning effect is introduced to characterize the decrease of processing times with the accumulation of the working experience. We assume that the set of jobs assigned to each due window is independent, and no inclusion exists between due windows. The objective is to determine the optimal due window positions and sizes, the set of jobs assigned to each due window, and the optimal schedule in each seru to minimize a multidimensional function, which consists of the earliness and tardiness punishment cost, as well as the due window related starting time and size cost. We find that when the number of jobs and the due windows assigned to each seru are pre-specified in advance, the problem can be solved in polynomial time. Meanwhile, the impacts of the due-window allocation strategy and learning effect on the total cost are respectively discussed based on numerical examples and special cases. The results show that if each seru is assigned with the same number of due windows, the total cost can be reduced with the increasing ratio of the due-window number to the to-be-processed job number. Furthermore, with an increasing learning effect, the total cost will be decreased.

Keywords

Scheduling / seru production system / due windows / learning effect

References

[1] Akino S. Internationalization of Japanese company and change of production system. Rikkyo Economic Review, 1997, 51: 29-55.

[2] Ayough A, Hosseinzadeh M, Motameni A. Job rotation scheduling in the seru system: Shake enforced invasive weed optimization approach. Assembly Automation, 2020, 40(3): 461-474.

[3] Bachman A, Janiak A. Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society, 2004, 55(3): 257-264.

[4] Bai D, Tang M, Zhang Z H, Santibanez-Gonzalez E D. Flow shop learning effect scheduling problem with release dates. Omega, 2018, 78: 21-38.

[5] Biskup D. Single-machine scheduling with learning considerations. European Journal of Operational Research, 1999, 188(2): 315-329.

[6] Biskup D. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 2008, 188(2): 315-329.

[7] Chen H, Luo X, Zhang Z, Zhou Q. Stochastic bi-level programming model for home healthcare scheduling problems considering the degree of satisfaction with visit time. Journal of Systems Science and Systems Engineering, 2021, 30(5): 572-599.

[8] Chen K, Li D, Wang X. Makespan minimization in two-machine flow-shop scheduling under no-wait and deterministic unavailable interval constraints. Journal of Systems Science and Systems Engineering, 2020, 29(4): 400-411.

[9] Cheng T C E, Wang G. Single machine scheduling with learning effect considerations. Annals of Operations Research, 2000, 98(1–4): 273-290.

[10] Cheng T C E, Yang S J, Yang D L. Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. International Journal of Production Economics, 2012, 135(1): 154-161.

[11] DeJong J R. The effects of increasing skill on cycle time and its consequences for time standards. Ergonomics, 1957, 1(1): 51-60.

[12] Fu Y P, Ding J L, Wang H F, Wang J W. Two-objective stochastic flow-shop scheduling with deteriorating and learning effect in industry 4.0-based manufacturing system. Applied Soft Computing, 2018, 68: 847-855.

[13] Gao J, Zhu X, Zhang R. A branch-and-price approach to the multitasking scheduling with batch control on parallel machines. International Transactions in Operational Research, 2022, 29(6): 3464-3485.

[14] Govindan K, Balasundaram R, Baskar N, Asokan P. A hybrid approach for minimizing makespan in permutation flowshop scheduling. Journal of Systems Science and Systems Engineering, 2017, 26(1): 50-76.

[15] Graham R L, Lawler E L, Lenstra J K, Kan AHGR. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 1979, 5: 287-326.

[16] Janiak A, Kovalyov M Y, Marek M. Soft due window assignment and scheduling on parallel machines. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2007, 37(5): 614-620.

[17] Janiak A, Rudek R. Experience-based approach to scheduling problems with the learning effect. IEEE Transactions on Systems, Man, and Cybernetics-part A: Systems and Humans, 2009, 39(2): 344-357.

[18] Ji M, Chen K, Ge J, Cheng T C E. Group scheduling and job-dependent due window assignment based on a common flow allowance. Computers & Industrial Engineering, 2014, 68(1): 35-41.

[19] Ji M, Yao D, Ge J, Cheng T C E. Single-machine slack due-window assignment and scheduling with past-sequence-dependent delivery times and control-lable job processing times. European J of Industrial Engineering, 2015, 9(6): 794.

[20] Ji M, Zhang W Y, Liao L J, Cheng T C E, Tan Y Y. Multitasking parallel-machine scheduling with machine dependent slack due-window assignment. International Journal of Production Research, 2019, 57(6): 1667-1684.

[21] Jiang Z, Chen F, Zhang X. Single-machine scheduling with times-based and job-dependent learning effect. Journal of the Operational Research Society, 2017, 68: 809-815.

[22] Kaku I, Gong J, Tang J, Yin Y. Modeling and numerical analysis of line-cell conversion problems. International Journal of Production Research, 2009, 47(8): 2055-2078.

[23] Kasm O A, Diabat A. The quay crane scheduling problem with non-crossing and safety clearance constraints: An exact solution approach. Computers & Operations Research, 2019, 107: 189-199.

[24] Koulamas C. Single-machine scheduling with time windows and earliness/tardiness penalties. European Journal of Operational Research, 1996, 91(1): 190-202.

[25] Koulamas C, Kyparisis G J. Single-machine and two-machine flowshop scheduling with general learning functions. European Journal of Operational Research, 2007, 178(2): 402-407.

[26] Kuo W H, Yang D L. Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. European Journal of Operational Research, 2006, 174(2): 1184-1190.

[27] Li Y, Li K, Yang Z, Yu Y, Xu R, Yang M. Stochastic optimal scheduling of demand response-enabled microgrids with renewable generations: An analytical-heuristic approach. Journal of Cleaner Production, 2022, 330: 129840.

[28] Liman S D, Panwalkar S S, Thongmee S. Common due window size and location determination in a single machine scheduling problem. Journal of the Operational Research Society, 1998, 49(9): 1007-1010.

[29] Liu C, Stecke K E, Lian J, Yin Y. An implementation framework for seru production. International Transactions in Operational Research, 2014, 21(1): 1-19.

[30] Luo L, Zhang Z, Yin Y (2016). Seru loading with worker-operation assignment in single period. AIEEE International Conference on Industrial Engineering and Engineering Management. Bali, Indonesia, December 29, 2016.

[31] Luo L, Zhang Z, Yin Y (2017). Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial and Management Optimization 13(5). DOI:https://doi.org/10.3934/jimo.2019134.

[32] Mor B. Single-machine minmax common due-window assignment and scheduling problems with convex resource allocation. Engineering Optimization, 2019, 51(7): 1251-1267.

[33] Mor B, Mosheiov G. Parallel machine scheduling problems with common flow-allowance. International Journal of Production Economics, 2012, 139(2): 623-633.

[34] Mosheiov G. Scheduling problems with a learning effect. European Journal of Operational Research, 2001, 132(3): 687-693.

[35] Mosheiov G, Sarig A. A due-window assignment problem with position-dependent processing times. Journal of the Operational Research Society, 2008, 59(7): 997-1003.

[36] Mosheiov G, Sarig A. Scheduling a maintenance activity and due-window assignment on a single machine. Computers & Operations Research, 2009, 36(9): 2541-2545.

[37] Papadimitriou C, Steiglitz K. Combinatorial optimization: Algorithms and complexity. IEEE Transactions on Acoustics Speech & Signal Processing, 1982, 32(6): 1258-1259.

[38] Pargar F, Zandieh M, Kauppila O, Kujala J. The effect of worker learning on scheduling jobs in a hybrid flow shop: A bi-objective approach. Journal of Systems Science and Systems Engineering, 2019, 27: 265-291.

[39] Peng Z, Zhang H, Tang H, Feng Y, Yin W. Research on flexible job-shop scheduling problem in green sustainable manufacturing based on learning effect. Journal of Intelligent Manufacturing, 2021, 33(6): 1725-1746.

[40] Pohl M, Artigues C, Kolisch R. Solving the time-discrete winter runway scheduling problem: A column generation and constraint programming approach. European Journal of Operational Research, 2022, 299(2): 674-689.

[41] Qureshi A G, Taniguchi E, Yamada T. An exact solution approach for vehicle routing and scheduling problems with soft time windows. Transportation Research Part E: Logistics and Transportation Review, 2009, 45(6): 960-977.

[42] Sakamaki H. The change of consciousness and company by cellular manufacturing in Canon way, 2006, Tokyo: JMAM

[43] Sakazume Y. Is Japanese cell manufacturing a new system? A comparative study between Japanese cell manufacturing and cellular manufacturing. Journal of Japan Industrial Management Association, 2005, 55(6): 341-349.

[44] Stecke K, Yin Y, Kaku I, Murase Y. Seru: The organizational extension of JIT for a super-talent factory. International Journal of Strategic Decision Sciences, 2012, 3(1): 105-118.

[45] Sun L, Yu A J, Wu B. Single machine common flow allowance group scheduling with learning effect and resource allocation. Computers & Industrial Engineering, 2006, 139: 106126.

[46] Tirkolaee E B, Aydin N S, Ranjbar-Bourani M, Weber G W. A robust bi-objective mathematical model for disaster rescue units allocation and scheduling with learning effect. Computers & Industrial Engineering, 2020, 149: 106790.

[47] Treville S, Ketokivi M, Singhal V. Competitive manufacturing in a high-cost environment: Introduction to the special issue. Journal of Operations Management, 2017, 49–51: 1-5.

[48] Villa A, Taurino T. From JIT to Seru, for a production as lean as possible. Procedia Engineering, 2013, 63: 956-965.

[49] Wang J B, Gao M, Wang J J, Liu L, He H. Scheduling with a position-weighted learning effect and job release dates. Engineering Optimization, 2020, 52(9): 1475-1493.

[50] Wang J B, Hu Y, Zhang B. Common due-window assignment for single-machine scheduling with generalized earliness/tardiness penalties and a rate-modifying activity. Engineering Optimization, 2021, 53(3): 1-17.

[51] Wang J B, Wang M Z. Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times. Asia-Pacific Journal of Operational Research, 2014, 31(5): 1450036.

[52] Wang J B, Xia Z Q. Flow-shop scheduling with a learning effect. Journal of the Operational Research Society, 2005, 56(11): 1325-1330.

[53] Wang L, Zhang Z, Yin Y (2019). Order acceptance and scheduling considering lot-spitting in seru production system. 2019 IEEE International Conference on Industrial Engineering and Engineering Management. Macau, China, December 15, 2019.

[54] Wang L Y, Wang J J, Wang J B, Feng E M. Scheduling jobs with general learning functions. Journal of Systems Science and Systems Engineering, 2011, 20(1): 119-125.

[55] Wang Y, Tang J. Cost and service-level-based model for a seru production system formation problem with uncertain demand. Journal of Systems Science and Systems Engineering, 2018, 27(4): 519-537.

[56] Wright T P. Factors affecting the cost of airplanes. Journal of the Aeronautical Sciences, 1936, 3: 122-128.

[57] Xue Z J, Zhang C R, Miao L X, Lin W H. An ant colony algorithm for yard truck scheduling and yard location assignment problems with precedence constraints. Journal of Systems Science and Systems Engineering, 2013, 22(1): 21-37.

[58] Yeung W K, Oguz C, Cheng T C E. Single-machine scheduling with a common due window. Computers & Operations Research, 2001, 28(2): 157-175.

[59] Yin Y, Stecke K E, Li D. The evolution of production systems from Industry 2.0 through Industry 4.0. International Journal of Production Research, 2018, 56(1–2): 848-861.

[60] Yin Y, Stecke K E, Swink M, Kaku I. Lessons from seru production on manufacturing competitively in a high cost environment. Journal of Operations Management, 2017, 49: 67-76.

[61] Ying K C, Lin S W, Lu C C. Effective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window. A International Journal of Production Research, 2017, 55(6): 1707-1719.

[62] Yu Y, Tang J. Review of seru production. Frontiers of Engineering Management, 2019, 6(2): 183-192.

[63] Zhang L, Deng Q, Lin R, Gong G, Han W. A combinatorial evolutionary algorithm for unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, limited worker resources and learning effect. Expert Systems with Applications, 2021, 175: 114843.

[64] Zhan R, Zhang J, Cui Z, Peng J, Li D (2021). An automatic heuristic design approach for seru scheduling problem with resource conflicts. Discrete Dynamics in Nature and Society: 8166343.

[65] Zhang X, Lin W, Hsu C, Wu C. Resource constrained scheduling problems with general truncated sum-of-processing time dependent effect under single machine and unrelated parallel machines. Computers & Industrial Engineering, 2017, 110: 344-352.

[66] Zhang X L, Liu C G, Li W J, Evans S, Yin Y. Effects of key enabling technologies for seru production on sustainable performance. Omega, 2017, 66: 290-307.

[67] Zhang Z, Gong X, Song X L, Yin Y, Lev B, Chen J. A column generation-based exact solution method for seru scheduling problems. Omega, 2022, 108: 102581.

[68] Zhang Z, Song X L, Huang H J, Zhou X, Yin Y. Logic-based Benders decomposition method for the seru scheduling problem with sequence-dependent setup time and DeJong’s learning effect. European Journal of Operational Research, 2022, 297(3): 866-877.

[69] Zhang Z, Wang L L, Song X L, Huang H J, Yin Y (2021). Improved genetic-simulated annealing algorithm for seru loading problem with downward substitution under stochastic environment. Journal of the Operational Research Society inpress. Doi:https://doi.org/10.1080/01605682.2021.1939172.