×

Applying available-to-promise (ATP) concept in mixed-model assembly line sequencing problems in a make-to-order (MTO) environment: problem extension, model formulation and Lagrangian relaxation algorithm. (English) Zbl 07319742

Summary: Mixed-model assembly line is known to be a special case of production lines where variety of product models similar to product characteristics are assembled. This article addresses available-to-promise (ATP) in mixed-model assembly line sequencing problems in a Make-To-Order environment in two stages. First, the customers are prioritized based on their corresponding profit values and a decision support system for order acceptance/rejection based on ATP is developed. By implementing this concept and developing a mathematical model, delivery quantity and date in a planning horizon are determined based on the inventories in the stock. The second stage is solving a mixed binary mathematical model to sequence accepted orders suitably according to demands due dates that guarantees the orders are not released too late or too early. The problem simultaneously considers following objectives: minimizing the total tardiness and earliness costs based on the determined priority of orders and minimizing the utility work and idle time of workers in the production line. An algorithm based on Lagrangian relaxation is developed for the problem, and tested in terms of solution quality and computational efficiency. To validate the performance of the proposed algorithm, various test problems in small size are solved using the CPLEX solver, and compared with the Lagrangian relaxation method. Finally, the proposed model is solved in large size problems to analyze the model performance. The drawback of the CPLEX is that it could not solve large problem instances in reasonable time. For the small sized problem, there is approximately 1% duality gap for the Lagrangian relaxation method. The maximum duality gap in the Lagrangian relaxation method for the large sized problem is always kept below 4% while the average computing time is very reasonable. Therefore, according to the results obtained from test problems, the developed Lagrangian relaxation method proved to be the suitable method for this problem.

MSC:

90Bxx Operations research and management science

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burns, LD; Daganzo, CF, Assembly line job sequencing principles, Int. J. Prod. Res., 25, 71-99 (1987)
[2] Dobson, G.; Yano, CA, Cyclic scheduling to minimize inventory in a batch flow line, Eur. J. Oper. Res., 75, 441-461 (1994) · Zbl 0806.90063
[3] Jafari Asl, A.; Solimanpur, M.; Shankar, R., Multi-objective multi-model assembly line balancing problem: a quantitative study in engine manufacturing industry, OPSEARCH, 44, 1-25 (2019) · Zbl 1471.90070
[4] Samouei, P.; Ashay, J., Developing optimization & robust models for a mixed-model assembly line balancing problem with semi-automated operations, Appl. Math. Model., 72, 259-275 (2019) · Zbl 1481.90160
[5] Leu, YY; Matheson, AL; Rees, LP, Sequencing mixed model assembly lines with genetic algorithms, Comput. Ind. Eng., 30, 1027-1036 (1996)
[6] Ho, J., A proposed approach for reconfiguration of flexible assembly line systems by motion genes, Int. J. Prod. Res., 43, 9, 1729-1749 (2005) · Zbl 1090.90062
[7] McMullen, PR; Frazier, GV, A simulated annealing approach to mixed-model sequencing with multiple objectives on a just-in-time line, IIE Trans., 32, 8, 679-686 (2000)
[8] Monden, Y., Toyota production system (1993), Peachtree Corners, GA: The Institute of Industrial Engineers, Peachtree Corners, GA
[9] Ghalehkhondabi, I.; Sormaz, D.; Weckman, G., Multiple customer order decoupling points within a hybrid MTS/MTO manufacturing supply chain with uncertain demands in two consecutive echelons, OPSEARCH, 53, 976-997 (2016) · Zbl 1360.90033
[10] Boysen, N.; Fliedner, M.; Scholl, A., Sequencing mixed-model assembly lines: survey, classification and model critique, Eur. J. Oper. Res., 192, 2, 349-373 (2009) · Zbl 1157.90405
[11] Thomopoulos, NT, Line balancing-sequencing for mixed model assembly, Manag. Sci., 14, 59-75 (1967)
[12] Öner-Közen, P.; Minner, S., Impact of priority sequencing decisions on on-time probability and expected tardiness of orders in make-to- order production systems with external due-dates, Eur. J. Oper. Res., 263, 2, 524-539 (2017) · Zbl 1380.90103
[13] Nazara, KP; Pillaib, V., Mixed-model sequencing problem under capacity and machine idle time constraints in JIT production systems, Comput. Ind. Eng., 118, 226-236 (2018)
[14] Rabbani, M.; Manavizadeh, N.; Shabanpour, N., Sequencing of mixed models on U-shaped assembly lines by considering effective help policies in make-to-order environment, Sci. Iran., 24, 3, 1493-1504 (2017)
[15] Rabbani, M., Rahimi-Vahed, A., Javadi, B., Tavakoli-Moghaddam, R.: A new approach for mixed model assembly line sequencing. In: Operations Research, pp. 169-74 (2006) · Zbl 1209.90144
[16] Bard, J.; Shtub, A.; Joshi, S., Sequencing mixed-model assembly lines to level parts usage and minimize line length, Int. J. Prod. Res., 32, 2431-2454 (1994) · Zbl 0902.90071
[17] Manavizadeh, N.; Tavakoli Moghaddam, R.; Rabbani, M.; Jolai, F., A multi-objective mixed-model assembly line sequencing problem in order to minimize total costs in a Make-To-Order environment, considering order priority, J. Manuf. Syst., 32, 124-137 (2013)
[18] Xiaobo, Z.; Ohno, K., Algorithms for sequencing mixed models on an assembly line in JIT prod, Comput. Ind. Eng., 32, 1, 47-56 (1997)
[19] McMullen, P., An JIT sequencing for mixed-model assembly lines with setups using tabu search production, Plan. Control, 9, 5, 504-510 (1998)
[20] Cho, HS; Paik, H.; Yoon, M.; Kima, HG, A robust design of simulated annealing approach for mixed-model sequencing, Comput. Ind. Eng., 48, 753-764 (2005)
[21] Altendorfer, K.; Jodlbauer, H., An analytical model for service level and tardiness in a single machine MTO production system, Int. J. Prod. Res., 49, 7, 1827-1850 (2011) · Zbl 1211.90066
[22] Macaskill, JLC, Computer simulation for mixed-model production lines, Manag. Sci., 20, 341-348 (1973)
[23] Miltenburg, J.; Goldstein, T., Developing production schedules which balance part usage and smooth production loads for just-in-time production systems, Naval Res Logist, 38, 893-910 (1991) · Zbl 0729.90951
[24] Pereira, J.; Vilà, M., An exact algorithm for the mixed-model level scheduling problem, Int. J. Prod. Res., 53, 5809-5825 (2015)
[25] Defersha, F.; Mohebalizadehgasht, F., Simultaneous balancing, sequencing, and workstation planning for a mixed model manual assembly line using hybrid genetic algorithm, Comput. Ind. Eng., 119, 370-387 (2018)
[26] Kinable, J.; Andre, A.; Cirec, W., Discrete Optimization, Hybrid optimization methods for time-dependent sequencing problems, Eur. J. Oper. Res., 259, 3, 887-897 (2017) · Zbl 1402.90053
[27] Keesari, HS; Rao, RV, Optimization of job shop scheduling problems using teaching-learning-based, OPSEARCH, 51, 4, 545-561 (2014) · Zbl 1332.90112
[28] Mozdgir, A.; Fatemi Ghomi, SMT; Jolai, F.; Navae, J., Three meta-heuristics to solve the no-wait two-stage assembly flow-shop scheduling problem, Sci. Iran., 20, 6, 2275-2283 (2013)
[29] Bautista, J.; Alfaro-Pozo, R., An expert system to minimize operational costs in mixed- model sequencing problems with activity factor, Expert Syst. Appl., 104, 185-201 (2018)
[30] Bautista, J.; Alfaro-Pozo, R., A GRASP Algorithm for Quota Sequences with Minimum Work Overload and Forced Interruption of Operations in a Mixed-Product Assembly Line (2018), Berlin: Springer, Berlin
[31] Mansouri, S., A multi-objective genetic algorithm for mixed-model sequencing on JIT assembly lines, Eur. J. Oper. Res., 167, 696-716 (2005) · Zbl 1077.90027
[32] Prasad, SD, A genetic algorithm for flowshop scheduling with multiple objectives, OPSEARCH, 44, 1, 1-16 (2007) · Zbl 1161.90398
[33] Rezaie, K., Eivazy, H., Nazari-Shirkouhi, S.: A novel release policy of hybrid make-to-stock/make-to-order semiconductor manufacturing systems. In: Second International Conference on Developments in Systems Engineering (2009)
[34] Xiaobo, Z.; Ohno, K., Properties of a sequencing problem for a mixed model assembly line with conveyor stoppages, Eur. J. Oper. Res., 124, 560-570 (2000) · Zbl 0969.90041
[35] Yano, CA; Bolat, A., Survey, development and applications of algorithms for sequencing paced assembly lines, J. Manuf. Oper. Manag., 2, 172-198 (1989)
[36] Bautista, J.; Companys, R.; Corominas, A., Heuristics and exact algorithms for solving the Monden problem, Eur. J. Oper. Res., 88, 101-113 (1996) · Zbl 0913.90159
[37] Miltenburg, J., Level schedules for mixed-model assembly lines in just-in-time productions systems, Manag. Sci., 35, 192-207 (1989) · Zbl 0666.90040
[38] Korkmazel, T.; Meral, S., Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems, Eur. J. Oper. Res., 13, 188-207 (2001) · Zbl 0979.90042
[39] Tamura, T.; Long, H.; Ohno, K., A sequencing problem to level part usage rates and work load for a mixed-model assembly line with a bypass subline, Int. J. Prod. Econ., 60, 557-564 (1999)
[40] Arredondo, F.; Martinez, E., Learning and adaptation of a policy for dynamic order acceptance in make-to-order manufacturing, Comput. Ind. Eng., 58, 70-83 (2010)
[41] Kalantari, M.; Rabbani, M.; Ebadian, M., A decision support system for order acceptance/rejection in hybrid MTS/MTO production systems, Appl. Math. Model., 35, 1363-1377 (2011) · Zbl 1211.90113
[42] Lee, Y.M.: Simulating impact of available-to-promise generation on supply chain performance. In: 38th Conference on Winter Simulation (2006)
[43] Uche, O.; Lauras, M.; Humez, V.; Dupont, L., Advanced available-to-promise for order management stock-out situation, Oper. Supply Chain Manag., 12, 101-114 (2008)
[44] Hosang, J., An available-to-promise model considering customer priority and variance of penalty costs, Int. J. Adv. Manuf. Technol., 49, 1-4, 369-377 (2010)
[45] Liu, Q.; Wang, W.; Zhu, K.; Zhang, C.; Rao, Y., Advanced scatter search approach and its application in a sequencing problem of mixed-model assembly lines in a case company, Eng. Optim., 46, 1485-1500 (2013)
[46] Frazier, G.; McMullen, P., A simulated annealing approach to mixed model sequencing with multiple objectives on a JIT line, IEE Trans., 32, 8, 679-686 (2000)
[47] Bautista, J.; Alfaro, R.; Bata, C., Modeling and solving the mixed-model sequencing problem to improve productivity, Int. J. Prod. Econ., 161, 83-95 (2015)
[48] Bautista, J.; Alfaro-Pozo, R.; Cristina, BG, Consideration of human resources in the mixed-model sequencing problem with work overload minimization: legal provisions and productivity improvement, Expert Syst. Appl., 42, 22, 8896-8910 (2015)
[49] Zhang, Y.; Luh, PB; Yoneda, K., Mixed-model assembly line scheduling using the Lagrangian relaxation technique, IIE Trans., 32, 125-134 (2000)
[50] Fisher, ML, The lagrangian relaxation method for solving integer programming problems, Manag. Sci., 27, 1-18 (1981) · Zbl 0466.90054
[51] Hyun, C.; Kim, Y.; Kim, Y., A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines, Comput. Oper. Res., 25, 675-690 (1998) · Zbl 1042.90553
[52] Beasley, J.; Reeves, CR, Lagrangian relaxation, Modern heuristic techniques for combinatorial problems, 243-303 (1993), New York: Wiley, New York · Zbl 0942.90500
[53] Bard, J.; Dar-El, E.; Shtub, A., An analytic framework for sequencing mixed model, Int. J. Prod. Res., 30, 1, 35-48 (1992) · Zbl 0825.90483
[54] Bard, JF; Shtub, A.; Joshi, SB, Sequencing mixed-model assembly lines to level parts usage and minimize the length, Int. J. Prod. Res., 32, 1, 2431-2454 (1994) · Zbl 0902.90071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.