本研究延伸彈性零工式排程問題，建立同時納入多資源限制、任意前後順序限制、三階段作業結構與階段省略機制的數學模型，並以最小化總完工時間為目標。模型以整備、加工與收尾三個階段描述每道作業，並將資源設定為直接執行階段的主動資源，以及作業期間需占用的被動資源，作業間允許多前置、分流與合流等非固定製程路徑。當不同工作中相同製程步驟的作業在同一主動資源上連續執行時，模型可依排序與資源指派結果，判斷是否省略前一作業的收尾階段與後一作業的整備階段，以表示連續生產中的狀態延續。本研究採用時間索引式模型描述各階段的執行狀態與資源占用，並以輔助變數完成線性化，同時加入強化限制式以排除不合理的階段排列，最後以 Gurobi 求解。模擬結果顯示，強化限制式使平均求解時間降低26.23%。相較於未導入階段省略的模型，平均總完工時間由37.29單位時間降至31.64 單位時間，降幅為15.14%，且90筆實例中有92.22% 取得較短總完工時間。結果顯示，階段省略機制能減少多餘整備與收尾時間，並使排程更貼近實際作業流程。

This study defines an extension of the flexible job shop scheduling problem that incorporates multiple resource constraints, arbitrary precedence relations, a three-phase operation structure, and a phase omission mechanism, with the objective of minimizing the makespan. Each operation consists of setup, processing, and cleaning phases. When operations of the same process step across different jobs are scheduled consecutively on the same active resource, the cleaning phase of the preceding operation and the setup phase of the following operation can be omitted, reflecting the continuity of tool configuration, machine state, or work environment. This study formulates the proposed problem as a time-indexed model, in which binary product terms and absolute value terms are linearized by auxiliary variables to obtain a mixed-integer linear programming model solved using Gurobi. Strengthening constraints exclude infeasible or invalid phase arrangements. The strengthening constraints reduce the average solving time by 26.23%. Compared with the model without phase omission, the average makespan decreases from 37.29 to 31.64, a reduction of 15.14%, and 92.22% of 90 test instances obtain shorter makespans.

[1] P. Brucker and R. Schlie, “Job-shop scheduling with multi-purpose machines,” Computing, vol. 45, no. 4, pp. 369–375, 1990.
[2] P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Annals of Operations Research, vol. 41, no. 3, pp. 157–183, 1993.
[3] J. Hurink, B. Jurisch, and M. Thole, “Tabu search for the job-shop scheduling problem with multi-purpose machines,” OR Spektrum, vol. 15, no. 4, pp. 205–215, 1994.
[4] M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research, vol. 1, no. 2, pp. 117–129, 1976.
[5] S. Dauzère-Pérès, J. Ding, L. Shen, and K. Tamssaouet, “The flexible job shop scheduling problem: A review,” European Journal of Operational Research, vol. 314, no. 2, pp. 409–432, 2024.
[6] S. Dauzère-Pérès, W. Roux, and J. B. Lasserre, “Multi-resource shop scheduling with resource flexibility,” European Journal of Operational Research, vol. 107, no. 2, pp. 289–305, 1998.
[7] G. Gong, R. Chiong, Q. Deng, and X. Gong, “A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility,” International Journal of Production Research, vol. 58, no. 14, pp. 4406–4420, 2020.
[8] Q. Luo, Q. Deng, G. Xie, and G. Gong, “A pareto-based two-stage evolutionary algorithm for flexible job shop scheduling problem with worker cooperation flexibility,” Robotics and Computer-Integrated Manufacturing, vol. 82, p. 102534, 2023.
[9] M. Liu, J. Lv, S. Du, Y. Deng, X. Shen, and Y. Zhou, “Multi-resource constrained flexible job shop scheduling problem with fixture–pallet combinatorial optimisation,” Computers & Industrial Engineering, vol. 188, p. 109903, 2024.
[10] Y. Zhou, S. Du, M. Liu, and X. Shen, “Machine-fixture-pallet resources constrained flexible job shop scheduling considering loading and unloading times under pallet automation system,” Journal of Manufacturing Systems, vol. 73, pp. 143–158, 2024.
[11] J. Li, Q. Liu, C. Wang, and X. Li, “A disjunctive graph-based metaheuristic for flexible job-shop scheduling problems considering fixture shortages in customized manufacturing systems,” Robotics and Computer-Integrated Manufacturing, vol. 95, p. 102981, 2025.
[12] M. R. Amin-Naseri and A. J. Afshari, “A hybrid genetic algorithm for integrated process planning and scheduling problem with precedence constraints,” The International Journal of Advanced Manufacturing Technology, vol. 59, no. 1, pp. 273–287, 2012.
[13] Z. Zhu and X. Zhou, “Flexible job-shop scheduling problem with job precedence constraints and interval grey processing time,” Computers & Industrial Engineering, vol. 149, p. 106781, 2020.
[14] G. A. Kasapidis, D. C. Paraskevopoulos, P. P. Repoussis, and C. D. Tarantilis, “Flexible job shop scheduling problems with arbitrary precedence graphs,” Production and Operations Management, vol. 30, no. 11, pp. 4044–4068, 2021.
[15] G. A. Kasapidis, S. Dauzère-Pérès, D. C. Paraskevopoulos, P. P. Repoussis, and C. D. Tarantilis, “On the multiresource flexible job-shop scheduling problem with arbitrary precedence graphs,” Production and Operations Management, vol. 32, no. 7, pp. 2322–2330, 2023.
[16] A. Allahverdi, C. T. Ng, T. C. E. Cheng, and M. Y. Kovalyov, “A survey of scheduling problems with setup times or costs,” European Journal of Operational Research, vol. 187, no. 3, pp. 985–1032, 2008.
[17] A. Allahverdi, “The third comprehensive survey on scheduling problems with setup times/costs,” European Journal of Operational Research, vol. 246, no. 2, pp. 345–378, 2015.
[18] M. Mousakhani, “Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness,” International Journal of Production Research, vol. 51, no. 12, pp. 3476–3487, 2013.
[19] L. Shen, S. Dauzère-Pérès, and J. S. Neufeld, “Solving the flexible job shop scheduling problem with sequence-dependent setup times,” European Journal of Operational Research, vol. 265, no. 2, pp. 503–516, 2018.
[20] E. H. Bowman, “The schedule-sequencing problem,” Operations Research, vol. 7, no. 5, pp. 621–624, 1959.
[21] J. P. Sousa and L. A. Wolsey, “A time indexed formulation of non-preemptive single machine scheduling problems,” Mathematical Programming, vol. 54, no. 1, pp. 353–367, 1992.
[22] F. Glover, “Improved linear integer programming formulations of nonlinear integer problems,” Management Science, vol. 22, no. 4, pp. 455–460, 1975.
[23] J. P. Vielma, “Mixed integer linear programming formulation techniques,” SIAM Review, vol. 57, no. 1, pp. 3–57, 2015.
[24] Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual, 2026. [Online]. Available: https://www.gurobi.com
[25] Y. Demir and S. K. İşleyen, “Evaluation of mathematical models for flexible job-shop scheduling problems,” Applied Mathematical Modelling, vol. 37, no. 3, pp. 977–988, 2013.
[26] W.-Y. Ku and J. C. Beck, “Mixed integer programming models for job shop scheduling: A computational analysis,” Computers & Operations Research, vol. 73, pp. 165–173, 2016.
[27] J. Roslöf, I. Harjunkoski, T. Westerlund, and J. Isaksson, “Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure,” European Journal of Operational Research, vol. 138, no. 1, pp. 29–42, 2002.
[28] S. F. Roselli, K. Bengtsson, and K. Åkesson, “SMT solvers for job-shop scheduling problems: Models comparison and performance evaluation,” in 2018 IEEE 14th International Conference on Automation Science and Engineering (CASE), pp. 547–552, 2018.
[29] IBM, IBM ILOG CPLEX Optimization Studio, ver. 22.2.0, 2026. [Online]. Available: https://www.ibm.com/docs/en/icos/22.2.0
[30] L. de Moura and N. Bjørner, “Z3: An efficient SMT solver,” in Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 337–340, 2008.
[31] H. Barbosa, C. Barrett, M. Brain, G. Kremer, H. Lachnitt, M. Mann, A. Mohamed, M. Mohamed, A. Niemetz, A. Nötzli, A. Ozdemir, M. Preiner, A. Reynolds, Y. Sheng, C. Tinelli, and Y. Zohar, “cvc5: A versatile and industrial-strength SMT solver,” in Proceedings of the 28th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 415–442, 2022.