Abstract
This paper focuses on seru scheduling problems considering the sequence-dependent setup time in seru production system, which is a new-type manufacturing system originated in Japanese production practice recently that can better adapt to the fluctuate market demand. A mixed integer programming (MIP) model with the objective of minimizing the sum of the makespan and the total weighted tardiness is constructed for the seru scheduling problem. The branch-and-bound (B&B) algorithm with two main steps is designed subsequently, where the first step solves the assignment of products to serus, while the second step solves the scheduling optimization in each seru. Finally, the computational experiments and comparative analysis with CPLEX 12.8 are made, and the report of results verifies that the effectiveness and practicability of the proposed MIP and B&B algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data availability
The authors confirm that the data supporting the findings of this study are available within the article [and/or its supplementary materials].
References
Abdeljaouad M, Bahroun Z, Omrane A, Fondrevelle J (2015) Job-shop production scheduling with reverse flows. Eur J Oper Res 244(1):1117–1128. https://doi.org/10.1016/j.ejor.2015.01.013
Abreu L, Cunha J, Prata B, Framinan J (2020) A genetic algorithm for scheduling open shops with sequence-dependent setup times. Comput Oper Res. https://doi.org/10.1016/j.cor.2019.104793
Afzalirad M, Shafipour M (2018) Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions. J Intell Manuf 29(2):423–437. https://doi.org/10.1007/s10845-015-1117-6
Akino S (1997) Internationalization of Japanese company and change of production system. Rikkyo Econ Rev 51(1):29–55 (in Japanese)
Allahverdi A (2015) The third comprehensive survey on scheduling problems with setup times/costs. Eur J Oper Res 246(2):345–378. https://doi.org/10.1016/j.ejor.2015.04.004
Allahverdi A, Soroush H (2008) The significance of reducing setup times/setup costs. Eur J Oper Res 187(3):978–984. https://doi.org/10.1016/j.ejor.2006.09.010
Allahverdi A, Gupta J, Aldowaisan T (1999) A review of scheduling research involving setup considerations. Omega-Int J Manag Sci 27(2):219–239. https://doi.org/10.1016/S0305-0483(98)00042-5
Allahverdi A, Ng C, Cheng T, Kovalyov M (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032. https://doi.org/10.1016/j.ejor.2006.06.060
Buxey G (1989) Production scheduling: practice and theory. Eur J Oper Res 39(1):17–31. https://doi.org/10.1016/0377-2217(89)90349-4
Cui W, Lu Z, Li C, Han X (2018) A proactive approach to solve integrated production scheduling and maintenance planning problem in flow shops. Comput Ind Eng 115:342–353. https://doi.org/10.1016/j.cie.2017.11.020
Gai Y, Yin Y, Tang J, Liu S (2020) Minimizing makespan of a production batch within concurrent systems: Seru production perspective. J Manag Sci Eng. https://doi.org/10.1016/j.jmse.2020.10.002
Gawiejnowicz S (2020) A review of four decades of time-dependent scheduling: main results, new topics, and open problems. J Sched 23(1):3–47. https://doi.org/10.1007/s10951-019-00630-w
Gmys J, Mezmaz M, Melab N, Tuyttens D (2020) A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem. Eur J Oper Res 284(3):814–833. https://doi.org/10.1016/j.ejor.2020.01.039
Iranpoor M, Fatemi S, Zandieh G (2012) Machine scheduling in the presence of sequence-dependent setup times and a rate-modifying activity. Int J Prod Res 50(24):7401–7414. https://doi.org/10.1080/00207543.2011.649801
Japan Machinery Federation (2005) Changes on manufacturing system and technologies. Japan Machinery Federation, Japan. (in Japanese)
Johnson S (1954) Optimal two-and three-stage production schedules with setup times included. Nav Res Logist 1(1):61–68. https://doi.org/10.1002/nav.3800010110
Kaku I, Gong J, Tang J, Yin Y (2009) Modelling and numerical analysis of line-cell conversion problems. Int J Prod Res 47(8):2055–2078. https://doi.org/10.1080/00207540802275889
Karlof JK (Ed) (2005) Integer programming: theory and practice. CRC Press
Kurz M, Askin R (2004) Scheduling flexible flow lines with sequence- dependent setup times. Eur J Oper Res 159(1):66–82. https://doi.org/10.1016/S0377-2217(03)00401-6
Lewis M (2019) Operations management: a research overview. Routledge, London
Lian J (2018) Seru production flexibility analysis and robust system construction. Xi’an University of Technology. (in Chinese)
Lian J, Liu C (2017) Research on order dispatching problem in view of multi-attribute matching. Sci Technol Manag Res 37(14):260–266 (in Chinese)
Lian J, Liu C, Li W, Yin Y (2018) A multi-skilled worker assignment problem in seruproduction systems considering the worker heterogeneity. Comput Ind Eng 118:366–382. https://doi.org/10.1016/j.cie.2018.02.035
Liu C, Li W, Lian J, Yin Y (2012) Reconfiguration of assembly systems: from conveyor assembly line to serus. J Manuf Syst 31(3):312–325. https://doi.org/10.1016/j.jmsy.2012.02.003
Liu C, Lian J, Yin Y, Li W (2010a) Seru seisan-an innovation of the production management mode in Japan. Asian J Technol Innov 18(2):89–113. https://doi.org/10.1080/19761597.2010.9668694
Liu C, Lian J, Yin Y, Li W (2010b) Seru Seisan-the latest manufacturing model developed in Japan. Manag Rev 22(05):93–103 (in Chinese)
Liu C, Stecke K, Lian J, Yin Y (2014) An implementation framework for seru production. Int Trans Oper Res 21(1):1–19. https://doi.org/10.1111/itor.12014
Liu C, Yang N, Li W, Lian J, Evans S, Yin Y (2013) Training and assignment of multi-skilled workers for implementing seruproduction systems. Int J Adv Manuf Technol 69(5–8):937–959. https://doi.org/10.1007/s00170-013-5027-5
Luo L, Zhang Z, Yin Y (2016) Seru loading with worker- operation assignment in single period. In: 2016 IEEE international conference on industrial engineering and engineering management (IEEM), pp 1055–1058. https://doi.org/10.1109/IEEM.2016.7798039.
Luo L, Zhang Z, Yin Y (2017) Modelling and numerical analysis of seru loading problem under uncertainty. Eur J Ind Eng 11(2):185–204. https://doi.org/10.1504/EJIE.2017.083255
Luo L, Zhang Z, Yin Y (2021) Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. J Ind Manag Optim 17(2):779–803. https://doi.org/10.3934/jimo.2019134
Miyake D (2006) The shift from belt conveyor line to work-cell based assembly systems to cope with increasing demand variation in Japanese industries. Int J Automot Technol Manag 6(4):419–439. https://doi.org/10.1504/IJATM.2006.012234
Mousakhani M (2013) Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness. Int J Prod Res 51(12):3476–3487. https://doi.org/10.1080/00207543.2012.746480
Reimann M, Schiltknecht P (2008) Studying the interdependence of contractual and operational flexibilities in the market of specialty chemicals. EurJ Oper Res 198(3):760–772. https://doi.org/10.1016/j.ejor.20-08.10.010
Ren H, Wang D (2019) Analysis of the effect of the line-seru conversion on the waiting time with batch arrival. Math Probl Eng. https://doi.org/10.1155/2019/4036794
Rocha P, Ravetti M, Mateus G, Pardalos P (2008) Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Comput Oper Res 35(4):1250–1264. https://doi.org/10.1016/j.cor.2006.07.015
Roth A, Singhal J, Singhal K, Tang S (2016) Knowledge creation and dissemination in operations and supply chain management. Prod Oper Manag 25(9):1473–1488. https://doi.org/10.1111/poms.12590
Sakazume Y (2005) Is Japanese cell manufacturing a new system?: a comparative study between Japanese cell manufacturing and cellular manufacturing (production and logistics). J Jpn Ind Manage Assoc 55(6):341–349. https://doi.org/10.11221/jima.55.341
Sakazume Y (2012) The organizing principles of assembly cells. Keio University Press, Tokyo ((in Japanese))
Shao L, Zhang Z, Yin Y (2016) A bi-objective combination optimisation model for line-seru conversion based on queuing theory. Int J Manuf Res 11(4):322–338. https://doi.org/10.1504/IJMR.2016.082821
Shen L, Dauzère-Pérès S, Neufeld J (2018) Solving the flexible job shop scheduling problem with sequence-dependent setup times. Eur J Oper Res 265(2):503–516. https://doi.org/10.1016/j.ejor.2017.08.021
Stecke K, Yin Y, Kaku I, Murase Y (2012) Seru: The organizational extension of JIT for a super-talent factory. Int J Strat Decis Sci 3(1):106–119. https://doi.org/10.4018/jsds.2012010104
Sun W, Yu Y, Lou Q, Wang J, Guan Y (2020) Reducing the total tardiness by Seru production: model, exact and cooperative coevolution solutions. Int J Prod Res 58(21):6441–6452. https://doi.org/10.1080/00207543.2019.1680898
Tang W, Yang H, Li Z, Guo J, Zhang S (2014) Non-identical parallel machine scheduling problem with energy and a tardiness cost. Software 35(03):52–57 (in Chinese)
Theodorakatos N (2018) Optimal phasor measurement unit placement for numerical observability using a two-phase branch-and-bound algorithm. Int J Emerg Electr Power Syst 19(3):20170231. https://doi.org/10.1515/ijeeps-2017-0231
Theodorakatos NP (2019) Optimal phasor measurement unit placement for numerical observability using branch-and-bound and a binary-coded genetic algorithm. Electr Power Compon Syst 47(4–5):357–371. https://doi.org/10.1080/15325008.2019.1605635
Theodorakatos NP, Lytras M, Babu R (2020) Towards smart energy grids: a box-constrained nonlinear underdetermined model for power system observability using recursive quadratic programming. Energies 13(7):1724. https://doi.org/10.3390/en13071724
Theodorakatos NP, Manousakis NM, Korres GN (2015) Optimal placement of phasor measurement units with linear and non-linear models. Electr Power Compon Syst 43(4):357–373. https://doi.org/10.1080/15325008.2014.981319
Treville S, Ketokivi M, Singhal V (2017) Competitive manufacturing in a high-cost environment: Introduction to the special issue. J Oper Manag 49–51:1–5. https://doi.org/10.1016/j.jom.2017.02.001
Trovinger S, Bohn R (2005) Setup time reduction for electronics assembly: combining simple (SMED) and IT-based methods. Prod Oper Manag 14:205–217. https://doi.org/10.1111/j.1937-5956.2005.tb00019.x
Wang Y, Tang J (2018) Cost and service-level-based model for a seru production system formation problem with uncertain demand. J Syst Sci Syst Eng 27(4):519–537. https://doi.org/10.1007/s115180185379-3
Weekly Toyo Keizai (2003) Not only Toyota-Miraculous Canon manufacturing system. Weekly Toyo Keizai, Japan. (in Japanese)
Xiong H, Li J, Kong J, Yang J, Jiang G (2006) Heuristic method for dynamic job shop scheduling problem with operation relativity. Chin J Mech Eng 8:50–55 (in Chinese)
Yaurima V, Burtseva L, Tchernykh A (2009) Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers. Comput Ind Eng 56(4):1452–1463. https://doi.org/10.1016/j.cie.2008.09.004
Yin Y, Stecke KE, Swink M, Kaku I (2012) Integrating lean and agile productionin a highly volatile environment with seru production systems: sony and Canon casestudies. Working paper, Yamagata University, Japan. (in Japanese)
Yin Y, Stecke K, Kaku I (2008) The evolution of seru production systems throughout Canon. Oper Manag Educ Rev 2:27–40. https://doi.org/10.4135/9781526462060
Yin Y, Stecke K, Li D (2018) The evolution of production systems from industry 2.0 through Industry 4.0. Int J Prod Res 56(1–2):848–861. https://doi.org/10.1080/00207543.2017.1403664
Yin Y, Stecke K, Swink M, Kaku I (2017) Lessons from seru production on manufacturing competitively in a high cost environment. J Oper Manag 49–51:67–76. https://doi.org/10.1016/j.jom.2017.01.003
Yu Y, Tang J (2018) Seru production mode. Science Press, Beijing (in Chinese)
Yu Y, Tang J (2019) Review of seru production. Front Eng Manag 6(2):183–192. https://doi.org/10.1007/s42524-019-0028-1
Yu Y, Tang J (2020) Design and optimization of seru production system. Science Press, BeiJing (in Chinese)
Yu Y, Gong J, Tang J, Yin Y, Kaku I (2012) How to do assembly line-cell conversion? a discussion based on factor analysis of system performance improvements. Int J Prod Res 50(18):5259–5280. https://doi.org/10.1080/00207543.2012.693642
Yu Y, Sun W, Tang J, Kaku I, Wang J (2017a) Line-seru conversion towards reducing worker(s) without increasing makespan: models, exact and meta-heuristic solutions. Int J Prod Res 55(10):2990–3007. https://doi.org/10.1080/00207543.2017.1284359
Yu Y, Sun W, Tang J, Wang J (2017b) Line-hybrid seru system conversion: models, complexities, properties, solutions and insights. Comput Ind Eng 103:282–299. https://doi.org/10.1016/j.cie.2016.11.035
Yu Y, Tang J, Gong J, Yin Y, Kaku I (2014) Mathematical analysis and solutions for multi-objective line-cell conversion problem. Eur J Oper Res 236(2):774–786. https://doi.org/10.1016/j.ejor.2014.01.029
Yu Y, Tang J, Sun W, Yin Y, Kaku I (2013) Reducing worker(s) by converting assembly line into a pure cell system. Int J Prod Econ 145(2):799–806. https://doi.org/10.1016/j.ijpe.2013.06.009
Yu Y, Tang J, Yin Y, Kaku I (2015) Comparison of two typical scheduling rules of line-seru conversion problem. Asian J Manag Sci Appl 2(2):154–170. https://doi.org/10.1504/AJMSA.2015.075337
Zhang X, Liu C, Li W, Evans S, Yin Y (2017) Effects of key enabling technologies for seru production on sustainable performance. Omega 66:290–307. https://doi.org/10.1016/j.omega.2016.-01.013
Zhang Z, Gong X, Song X, Yin Y, Lev B, Chen J (2022a) A column generation-based exact solution method for seru scheduling problems. Omega 108:102581. https://doi.org/10.1016/j.omega.2021.102581
Zhang Z, Song X, Huang H, Yin Y, Lev B (2022b) Scheduling problem in seru production system considering DeJong’s learning effect and job splitting. Ann Oper Res 312:1119–1141. https://doi.org/10.1007/s10479-021-04515-0
Zhang Z, Song XL, Huang HJ, Zhou XY, Yin Y (2022c) Logic-based Benders decomposition method for the seru scheduling problem with sequence-dependent setup time and DeJong’s learning effect. Eur J Oper Res 297:866–877. https://doi.org/10.1016/j.ejor.2021.06.017
Zhang Z, Song X, Gong X, Yin Y, Lev B, Zhou X (2022d) An exact quadratic programming approach based on convex reformulation for seru scheduling problems. Nav Res Logist 69:1096–1107. https://doi.org/10.1002/nav.22078
Zhang Z, Wang L, Song X, Huang H, Yin Y (2022e) Improved genetic-simulated annealing algorithm for seru loading problem with downward substitution under stochastic environment. J Oper Res Soc 73(8):1800–1811. https://doi.org/10.1080/01605682.2021.1939172
Zhang Z, Song X, Gong X, Yin Y, Lev B, Zhou X (2022f) An effective heuristic based on 3-opt strategy for seru scheduling problems with learning effect. Int J Prod Res. https://doi.org/10.1080/00207543.2022.2054744
Funding
This study was funded by the Fundamental Research Funds for the Central Universities (No. 30922011406), and the System Science and Enterprise Development Research Center (Grant No. Xq22B06).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhang, X., Zhang, Z., Gong, X. et al. An exact branch-and-bound algorithm for seru scheduling problems with sequence-dependent setup time. Soft Comput 27, 6415–6436 (2023). https://doi.org/10.1007/s00500-023-07846-1
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-023-07846-1