在製造業中，生產排程問題是複雜且困難的，通常都是規模足夠大且毛利足夠高的科技業才足以支應高額的生產排程軟體費用及軟體維護之人力成本。然而在中小型的傳統製造業中，其生產排程複雜度已不是人工安排能夠完善處理的。以研究個案車用扣件廠為例，常因人工安排的低時效性及低正確性，導致錯誤的決策。因利潤不足，或對排程技術的不認識，以致於遲遲沒有導入電腦化排程，仍以人工安排而陷入生產效率低落的惡性循環。因此本研究提出一個排程方法，使得研究個案車用扣件廠能使用該方法，得到以最小化排程總製造時間(makespan)為目標的近似最佳排程。本研究問題為部份路徑彈性零工式排程問題(partial path flexibility job shop scheduling problem, PPFJSSP)，其問題特色除了具備零工式排程問題(job shop scheduling problem, JSSP)之特色：各工作之工序不盡相同，部份路徑彈性零工式排程問題本身還具有各工作站擁有多台平行機器，但每台機器所能加工的工作不盡相同之特色。本研究基於二個傳統的排程問題之混整數模型：排序(rank-based)模型、互斥(disjunctive)模型，調整成部份路徑彈性零工式排程之模型，以數個案例比較求解結果後推論互斥模型所調整成的部份路徑彈性零工式排程模型較佳。並使用此模型於小規模問題求得最佳解，再以基於部份路徑彈性零工式排程模型的多階段平行機器排程演算法和基於部份路徑彈性零工式排程模型的貪婪混合模型演算法求出近似最佳解，比較二者近似最佳解與部份路徑彈性零工式排程模型最佳解的差距。結果顯示基於部份路徑彈性零工式排程模型的貪婪混合模型演算法為較佳的演算法。本研究以一車用扣件廠為案例，使用部份路徑彈性零工式排程模型與貪婪混合模型演算法代入10筆個案公司的訂單資料求解排程與分析，其中包含5筆小規模問題與5筆大規模問題。將二方法求解時間限制為600秒，以部份路徑彈性零工式排程模型計算86400秒所得之解充當最佳解，作為二方法比較的基準點。結果表明個案公司較大問題規模的生產線使用貪婪混合模型演算法所計算出的解與最佳解的差距，能較部份路徑彈性零工式排程模型所計算出的解與最佳解的差距平均減少2.39%。

This thesis develops a greedy mixed model algorithm based on a greedy algorithm and a mixed integer programming (MIP) model to provide a better approximate optimal solution for the partial path flexibility job shop scheduling problem (PPFJSSP) with minimizing the makespan. We adjust two classical MIP formulations for scheduling problems to the PPFJSSP form: the rank-based formulation and the disjunctive formulation. The case of a car fastener manufacturing company is used for illustration. Our preliminary experimental results reveal that the disjunctive model performs better than the rank-based model, comparing the two formulations on many instances of the case study. Therefore, we develop a multi-stage parallel machine scheduling algorithm and a greedy mixed model algorithm, based on the disjunctive model for PPFJSSP. The further results indicate that the greedy mixed model algorithm is better. It calculates the gap of the approximate optimal solution by the multi-stage parallel machine scheduling algorithm and the optimal solution of the PPFJSSP model, as well as the gap of the approximate optimal solution by the greedy mixed model algorithm and the optimal solution of the PPFJSSP model, then comparing them. Lastly, we compare the performance of the greedy mixed model algorithm with the PPFJSSP model on 10 instances, including 5 small-scale and 5 large-scale, of the case study within a time limit of 600 seconds for each trial. We consider the approximate optimal solution of the PPFJSSP model obtained within a time limit of 86400 seconds as the optimal solution and benchmark for the comparison. The results show the difference of the two gaps reduced by 2.39% on average on the large-scale instances.

Bowman, E. H. (1959). The schedule-sequencing problem. Operations Research, 7(5), 621-624.

Cheng, T. C. E., & Sin, C. C. S. (1990). A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research, 47(3), 271-292.

French, S. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job-shop. Chichester, U.K.: Ellis Horwood.

Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117-129.

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, Vol. 5, pp. 287-326.

Gurobi Optimization. (2020). Any Good Practice for Using Big M. Gurobi Help Center. Retrieved from https://support.gurobi.com/hc/en-us//community/posts/360074623951-Any-good-practice-for-using-bigM-(Last visited November 28, 2022).

IBM ILOG CPLEX optimization studio. (2018). Difference between using indicator constraints and a big-M formulation. IBM Support. Retrieved from https://www.ibm.com/support/pages/difference-between-using-indicator-constraints-and-big-m-formulation (Last visited November 28, 2022).

Kondili, E., & Sargent, R. W. H. (1988). A general algorithm for scheduling batch operations.Technical Report. Centre for Process Systems Engineering, Imperial College of Science, Technology and Medicine. London, U.K.

Ku, W. Y., & Beck, J. C. (2016). Mixed integer programming models for job shop scheduling: A computational analysis. Computers & Operations Research, 73, 165-173.

Liao, C. J., & You, C. T. (1992). An improved formulation for the job-shop scheduling problem. Journal of the Operational Research Society, 43(11), 1047-1054.

Laguna, M. (1999). A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times. IIE Transactions, 31(2), 125-134.
Manne, A. S. (1960). On the job-shop scheduling problem. Operations Research, 8(2), 219-223.

Mellor, P. (1966). A review of job shop scheduling. Journal of the Operational Research Society, 17(2), 161-171.

Pan, C. H. (1997). A study of integer programming formulations for scheduling problems. International Journal of Systems Science, 28(1), 33-41.

Ronconi, D. P., & Birgin, E. G. (2012). Mixed-integer programming models for flowshop scheduling problems minimizing the total earliness and tardiness. In Rios, R., & Ríos-Solís, Y. A. (Eds.), Just-in-Time Systems, pp. 91-105. New York, NY: Springer.

Rubin, P. A. (2018). Choosing "Big M" values. Retrieved from https://orinanobworld.blogspot.com/2018/09/choosing-big-m-values.html (Last visited November 28, 2022).

Shen, L., Dauzère-Pérès, S., & Neufeld, J. S. (2018). Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 265(2), 503-516.

Vilcot, G., & Billaut, J. C. (2008). A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem. European Journal of Operational Research, 190(2), 398-411.

Wagner, H. M. (1959). An integer linear‐programming model for machine scheduling. Naval Research Logistics Quarterly, 6(2), 131-140.

Wilbrecht, J. K., & Prescott, W. B. (1969). The influence of setup time on job shop performance. Management Science, 16(4), B-274.

Wilson, J. M. (1989). Alternative formulations of a flow-shop scheduling problem. Journal of the Operational Research Society, 40(4), 395-399.

Xiong, H., Shi, S., Ren, D., & Hu, J. (2022). A survey of job shop scheduling problem: The types and models. Computers & Operations Research, 105731.