流程型生產排程問題之混合整數規劃模式

MILP Models for Flowshop Scheduling Problems

劉建杰(Jiam-Jie Liou)

指導教授 ： 應國卿

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2010年)

摘要

流程型生產排程問題(Permutation Flowshop Scheduling Problem; PFSP)為生產製造的重要問題，流程型工廠排程問題中，決策者為了達成提昇系統績效之目標，除了要使產出時間儘量降低之外，還必需同時考慮使在製品庫存水準儘量降低、機器稼動率以及準時達交。
本研究主要在探討n件工作m台機器之流程型生產問題，並使用二元整數作為混合整數線性規劃之整數變數。大多數的生產排程問題都在探討單一準則，然而排程問題常常有多方面的考量與分析之多準則分析。在本研究中，考慮n件工作m台機器之多準則流程型生產問題。其追求目標函數分別為：即最大完工時間(Makespan)、總完成時間(Total Complete Time)、總延遲時間(Total Tardiness Time)、最大延遲時間( )、總機器閒置時間(Total Machine Idle Time)以及總工作等待時間(Total Job Wait Time)。
本研究首先建構MPFSP的混合整數規劃(MILP)數學模型，然後以LINGO套裝軟體進行模型編碼，最後由LINGO套裝軟體求解。為驗證所提出之MILP模式的求解績效，本研究將以文獻提供的標準題庫進行測試，結果顯示本研究之所提出的MPFSP最佳化生產排程模式之求解績效十分良好，可供相關業者生產排程之參考，藉以提升企業的競爭力與獲利能力。

關鍵字

流程型生產 ； 混合整數規劃

並列摘要

Permutation Flowshop Scheduling Problem (PFSP) is an important issue in manufacturing. To improve the system performance, the decision makers need to reduce process time and inventory level, enhance ratio of utilization, and delivery on time.
The problem of an n-job, m-machine Flowshop Scheduling Problem is discussed. A mixed-integer linear program (MILP) is formulated with considerably reduced number of integer binary variables.
Most of research in production scheduling is concerned with the minimization of a single criterion. However, scheduling problems often involve more than one aspect and therefore require multicriteria analysis. In this study, a multicriteria an n-job, m-machine flowshop scheduling problem is considered. The objective function of the problem is minimization of the makespan, total complete time, total tardiness time, maximum tardiness time, total machine idle time, and total job wait time.
This research first creates a mathematical MILP model of MPFSP, and then computes this model by LINGO. To validate the effectiveness of the proposed model, this research uses the earlier studies as benchmarks to compare with the result of this study. In the comparison result, it is appeared that the effectiveness of the proposed model is well, and it can be used as valuable reference for practitioners to improve their operational efficiency within a reasonable amount of computational effort.

並列關鍵字

Flowshop ； Mixed-Integer Linear Programming

參考文獻

[1] K. R. Baker and Wiley, "Introduction to Sequencing and Scheduling," New York, 1974.

[2] H. V. D. Parunak, "Characterizing the Manufacturing Scheduling Problem," Journal of Manufacturing Systems, Vol.. 10, No. 3, 1991, PP. 241–259.

[3] S. A. Brah and J. L. Hunsucker, "Branch and bound algorithm for the flow shop with multiple processors," European Journal Operational Research, Vol.. 51, No. 3, 1991, PP. 88–99.

[4] Z. A. Lomnicki, "A branch and bound algorithm for the exact solution of the three-machine scheduling problem," Operation Research Quarterly, Vol. 16, No.1, 1965, PP. 89–100.

[5] A. Allahverdi and F. S. Al-Anzi, "A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times," European Journal of Operational Research, Vol. 169, No. 3, 2006, PP. 767–780.