Just-in-time scheduling problem with due windows and release dates for precast bridge girders. (English) Zbl 07816767
Summary: As the prefabrication construction method plays an increasingly important role in the construction of cross-sea bridges, coordinating the schedule between off-site prefabrication and on-site assembly becomes crucial and challenging. This paper studies a just-in-time single-machine scheduling problem with due windows and release dates, which originates from the production and supply process of large segments of precast steel box girders in bridge construction. To solve this problem, we equivalently decompose it into the independent and same type of subproblems and formulate a mixed-integer linear mathematical programming model. Furthermore, we propose a branch-and-bound algorithm with the initialization of a novel linear early and tardy dispatching rule with due windows to solve the problem exactly. The dispatching rule, based on the local dominance criteria with due windows, is designed and used to improve the upper bound. Moreover, a lower bound is obtained by further decomposing and relaxing the subproblems. Finally, the parameter of the dispatching rule is calibrated, and the best search strategy of the branch-and-bound algorithm is determined. The comprehensive computational experiments carried out show the efficiency and effectiveness of the proposed branch-and-bound algorithm.
© 2024 International Federation of Operational Research Societies.
© 2024 International Federation of Operational Research Societies.
MSC:
| 90-XX | Operations research, mathematical programming |
Keywords:
just-in-time scheduling; due windows; release dates; steel box girders; dispatching rules; branch-and-boundReferences:
| [1] | deAraújo, K.A.G., Bonates, T.O., Prata, B.A., 2021a. The integrated cutting and packing heterogeneous precast beams multiperiod production planning problem. RAIRO —Operations Research55, 4, 2491-2524. · Zbl 1479.90172 |
| [2] | deAraújo, K.A.G., Bonates, T.O., Prata, B.A., Pitombeira‐Neto, A.R., 2021b. Heterogeneous prestressed precast beams multiperiod production planning problem: modeling and solution methods. TOP29, 3, 660-693. · Zbl 1476.90277 |
| [3] | Arroyo, J.E.C., dos Santos Ottoni, R., dePaiva Oliveira, A., 2011. Multi‐objective variable neighborhood search algorithms for a single machine scheduling problem with distinct due windows. Electronic Notes in Theoretical Computer Science281, 5-19. |
| [4] | Babalola, O., Ibem, E.O., Ezema, I.C., 2019. Implementation of lean practices in the construction industry: a systematic review. Building and Environment148, 34-43. |
| [5] | Baker, K.R., Scudder, G.D., 1990. Sequencing with earliness and tardiness penalties: a review. Operations Research38, 1, 22-36. · Zbl 0699.90052 |
| [6] | Behnamian, J., Zandieh, M., Fatemi Ghomi, S., 2009. Due window scheduling with sequence‐dependent setup on parallel machines using three hybrid metaheuristic algorithms. The International Journal of Advanced Manufacturing Technology44, 7, 795-808. |
| [7] | Boschetti, M.A., Letchford, A.N., Maniezzo, V., 2023. Matheuristics: survey and synthesis. International Transactions in Operational Research30, 6, 2840-2866. · Zbl 07745315 |
| [8] | Brucker, P., 2007. Scheduling Algorithms (5th edn.). Springer, Berlin. · Zbl 1126.90001 |
| [9] | Chou, F.D., Chang, T.Y., Lee, C.E., 2005. A heuristic algorithm to minimize total weighted tardiness on a single machine with release times. International Transactions in Operational Research12, 2, 215-233. · Zbl 1063.90026 |
| [10] | Du, J., Leung, J.Y.T., 1990. Minimizing total tardiness on one machine is NP‐hard. Mathematics of Operations Research15, 3, 483-495. · Zbl 0714.90052 |
| [11] | Đurasević, M., Jakobović, D., 2020. Comparison of schedule generation schemes for designing dispatching rules with genetic programming in the unrelated machines environment. Applied Soft Computing96, 106637. |
| [12] | Gao, W.B., Su, Q.K., Zhang, J.W., Xie, H.B., Wen, F., Li, F., Liu, J.Z., 2020. Steel bridge construction of Hong Kong-Zhuhai-Macao Bridge. International Journal of Steel Structures20, 5, 1498-1508. |
| [13] | Gui, L., Xie, Y., Wang, H.W., 2017. Early/tardy scheduling problem for the steel box girders production and construction. Systems Engineering - Theory & Practice37, 5, 1274-1281. |
| [14] | Hall, N.G., Kubiak, W., Sethi, S.P., 1991. Earliness– tardiness scheduling problems, II: deviation of completion times about a restrictive common due date. Operations Research39, 5, 847-856. · Zbl 0762.90037 |
| [15] | Hall, N.G., Posner, M.E., 1991. Earliness‐tardiness scheduling problems, I: weighted deviation of completion times about a common due date. Operations Research39, 5, 836-846. · Zbl 0749.90041 |
| [16] | Hoogeveen, J.A., van deVelde, S.L., 1996. A branch‐and‐bound algorithm for single‐machine earliness– tardiness scheduling with idle time. INFORMS Journal on Computing8, 4, 402-412. · Zbl 0884.90102 |
| [17] | Janiak, A., Janiak, W., Januszkiewicz, R., 2009. Algorithms for parallel processor scheduling with distinct due windows and unit‐time jobs. Bulletin of the Polish Academy of Sciences: Technical Sciences57, 3. |
| [18] | Jeong, B., Kim, Y.D., Shim, S.O., 2020. Algorithms for a two‐machine flowshop problem with jobs of two classes. International Transactions in Operational Research27, 6, 3123-3143. · Zbl 07767668 |
| [19] | Jing, X.L., Pan, Q.K., Gao, L., Wang, Y.L., 2020. An effective iterated greedy algorithm for the distributed permutation flowshop scheduling with due windows. Applied Soft Computing96, 106629. |
| [20] | Keshavarz, T., Savelsbergh, M., Salmasi, N., 2015. A branch‐and‐bound algorithm for the single machine sequence‐dependent group scheduling problem with earliness and tardiness penalties. Applied Mathematical Modelling39, 20, 6410-6424. · Zbl 1443.90041 |
| [21] | Khare, A., Agrawal, S., 2019. Scheduling hybrid flowshop with sequence‐dependent setup times and due windows to minimize total weighted earliness and tardiness. Computers & Industrial Engineering135, 780-792. |
| [22] | Kianfar, K., Moslehi, G., 2012. A branch‐and‐bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties. Computers & Operations Research39, 12, 2978-2990. · Zbl 1349.90364 |
| [23] | Kong, L., Li, H., Luo, H., Ding, L., Luo, X., Skitmore, M., 2017. Optimal single‐machine batch scheduling for the manufacture, transportation and JIT assembly of precast construction with changeover costs within due dates. Automation in Construction81, 34-43. |
| [24] | Koulamas, C., 1996. Single‐machine scheduling with time windows and earliness/tardiness penalties. European Journal of Operational Research91, 1, 190-202. · Zbl 0947.90588 |
| [25] | Li, G., 1997. Single machine earliness and tardiness scheduling. European Journal of Operational Research96, 3, 546-558. · Zbl 0917.90194 |
| [26] | Li, Z., Shen, G.Q., Xue, X., 2014. Critical review of the research on the management of prefabricated construction. Habitat International43, 240-249. |
| [27] | Liaw, C.F., 1999. A branch‐and‐bound algorithm for the single machine earliness and tardiness scheduling problem. Computers & Operations Research26, 7, 679-693. · Zbl 0957.90061 |
| [28] | Mahnam, M., Moslehi, G., 2009. A branch‐and‐bound algorithm for minimizing the sum of maximum earliness and tardiness with unequal release times. Engineering Optimization41, 6, 521-536. |
| [29] | Monden, Y., 2011. Toyota Production System: An Integrated Approach to Just‐In‐Time (4th edn). CRC Press, Boca Raton, FL. |
| [30] | Mrad, M., Chalghoumi, S., Ladhari, T., Gharbi, A., 2019. Enhanced lower bounds and exact procedures for total completion time minimization in a two‐machine permutation flowshop with release dates. International Transactions in Operational Research26, 6, 2432-2449. · Zbl 07766402 |
| [31] | Ou, Z., Xie, M., Lin, S., Lin, W., 2018. The practice and development of prefabricated bridges. IOP Conference Series: Materials Science and Engineering, Vol. 392, IOP Publishing, Bristol, pp. 62-86. |
| [32] | Ow, P.S., Morton, T.E., 1989. The single machine early/tardy problem. Management Science35, 2, 177-191. · Zbl 0666.90043 |
| [33] | Prata, B.d.A., Pitombeira‐Neto, A.R., deMoraes Sales, C.J., 2015. An integer linear programming model for the multiperiod production planning of precast concrete beams. Journal of Construction Engineering and Management141, 10, 04015029. |
| [34] | Qi, C., Lu, H., Wang, H.W., Yong, X., Wei, Z., Zhang, J.W., 2019. Factory‐based construction management innovation in major projects: integrated management and supplier cultivation. Management World35, 4, 39-51. |
| [35] | Ribeiro, F.F., deSouza, S.R., Souza, M.J., Gomes, R.M., 2010. An adaptive genetic algorithm to solve the single machine scheduling problem with earliness and tardiness penalties. IEEE Congress on Evolutionary Computation, IEEE, Piscataway, NJ, pp. 1-8. |
| [36] | Rodrigues, F., Agra, A., 2024. Handling uncertainty in the quay crane scheduling problem: a unified distributionally robust decision model. International Transactions in Operational Research31, 2, 721-748. · Zbl 07797294 |
| [37] | Rosa, B.F., Souza, M.J.F., deSouza, S.R., deFrança Filho, M.F., Ales, Z., Michelon, P.Y.P., 2017. Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties. Computers & Operations Research81, 203-215. · Zbl 1391.90308 |
| [38] | Sarhani, M., Voß, S., Jovanovic, R., 2023. Initialization of metaheuristics: comprehensive review, critical analysis, and research directions. International Transactions in Operational Research30, 6, 3361-3397. · Zbl 07745330 |
| [39] | Schaller, J., Valente, J., 2019. Branch‐and‐bound algorithms for minimizing total earliness and tardiness in a two‐machine permutation flow shop with unforced idle allowed. Computers & Operations Research109, 1-11. · Zbl 1458.90355 |
| [40] | Sidney, J.B., 1977. Optimal single‐machine scheduling with earliness and tardiness penalties. Operations Research25, 1, 62-69. · Zbl 0383.90055 |
| [41] | Signorini, C.d.A., deAraujo, S.A., Melega, G.M., 2022a. One‐dimensional multi‐period cutting stock problems in the concrete industry. International Journal of Production Research60, 8, 2386-2403. |
| [42] | Signorini, C.d.A., deAraujo, S.A., Poltroniere, S.C., Melega, G.M., 2022b. One‐dimensional multi‐period cutting stock problem with two stages applied to lattice slab production. Journal of the Operational Research Society. https://doi.org/10.1080/01605682.2022.2085067. · doi:10.1080/01605682.2022.2085067 |
| [43] | Sourd, F., 2009. New exact algorithms for one‐machine earliness‐tardiness scheduling. INFORMS Journal on Computing21, 1, 167-175. · Zbl 1243.90071 |
| [44] | Sourd, F., Kedad‐Sidhoum, S., 2003. The one‐machine problem with earliness and tardiness penalties. Journal of Scheduling6, 6, 533-549. · Zbl 1154.90490 |
| [45] | Sourd, F., Kedad‐Sidhoum, S., 2008. A faster branch‐and‐bound algorithm for the earliness‐tardiness scheduling problem. Journal of Scheduling11, 1, 49-58. · Zbl 1168.90471 |
| [46] | Sugimori, Y., Kusunoki, K., Cho, F., Uchikawa, S., 1977. Toyota production system and Kanban system materialization of just‐in‐time and respect‐for‐human system. International Journal of Production Research15, 6, 553-564. |
| [47] | Sundar, S., Singh, A., 2012. A swarm intelligence approach to the early/tardy scheduling problem. Swarm and Evolutionary Computation4, 25-32. |
| [48] | Valente, J., 2005. Improved lower bounds for the single machine earliness/tardiness scheduling problem with release dates. International Journal of Operations Research2, 2, 9-16. · Zbl 1115.90343 |
| [49] | Valente, J.M., Alves, R.A., 2005. An exact approach to early/tardy scheduling with release dates. Computers & Operations Research32, 11, 2905-2917. · Zbl 1071.90541 |
| [50] | Valente, J.M., Alves, R.A., 2007. Heuristics for the early/tardy scheduling problem with release dates. International Journal of Production Economics106, 1, 261-274. |
| [51] | Wan, G.H., Yen, B.P.C., 2002. Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. European Journal of Operational Research142, 2, 271-281. · Zbl 1082.90531 |
| [52] | Wang, L., Zhao, Y., Yin, X., 2023. Precast production scheduling in off‐site construction: mainstream contents and optimization perspective. Journal of Cleaner Production405, 137054. |
| [53] | Xie, Y., Wang, H., Liu, G., Lu, H., 2023. Just‐in‐time precast production scheduling using dominance rule‐based genetic algorithm. IEEE Transactions on Neural Networks and Learning Systems34, 9, 5283-5297. |
| [54] | Xiong, F., Chu, M., Li, Z., Du, Y., Wang, L., 2021. Just‐in‐time scheduling for a distributed concrete precast flow shop system. Computers & Operations Research129, 105204. · Zbl 1510.90131 |
| [55] | Yoo, W.S., Martin‐Vega, L., 2001. Scheduling single‐machine problems for on‐time delivery. Computers & Industrial Engineering39, 3-4, 371-392. |
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.
