利用限制規劃解決相同平行機台可分割排程問題

Using Constraint Programming To Solve Identical Parallel Machine Preemptive Scheduling

李國璋(Guo-Jang Li)

指導教授 ： 高有成

大同大學/經營設計學院/資訊經營學系所/碩士(2004年)

摘要

本研究主旨在探討相同平行機台可分割排程問題。該類問題在過去的文獻大多只考慮工單下放時間或交期其中一種，已經不符合目前生產系統的排程要求。所以本研究針對該類問題，同時考慮不同的工單下放時間與交期，目標是總流程時間最小化。本研究結合限制推演方法與基因演算法進行求解，命名為CPGA，目的是利用限制推演演算法值域刪減的特性，可快速找出合理解，再透過基因演算法的全域搜尋能力，找出近似最佳解。由於利用基因演算法解決平行機台可分割排程問題，染色體的資訊變得非常複雜且長度不一，因此本研究重新設計染色體Table示法，可有效地解決此類問題。
在驗證比較部分，針對規則與不規則兩種工作參數型態進行實驗，與傳統的SRPT方法進行比較。實驗結果發現，在工作參數為規則時，本研究所提出的CPGA與SRPT一樣可求得最佳解。在工作參數不規則時，依照工作大小與工作可排入時段鬆緊程度，隨機產生工作案例進行實驗。實驗結果發現，對中小型問題，CPGA可求得較佳的解且不會違反交期限制，但在大型問題時則比SRPT稍差。因此可以推論本研究所提的方法論，確實可以解決多限制式的平行機台可分割排程問題。

關鍵字

平行機台排程 ； 可分割排程問題 ； 基因演算法 ； 限制規劃

並列摘要

This research is aimed to study identical parallel machine preemptive scheduling problem. This issue was only studied with either release time or deadline in previous literatures. And that cannot fulfill the scheduling request of current production system. Therefore, this study is focused on this issue, considering both different release time and deadline, and the objective function is to minimize total flow time. This study combines constraint propagation and genetic algorithm, which is named CPGA, to find the solution. The goal is to use the characteristic of domain reduction of constraint propagation algorithm to find the feasible solution quickly; then find the approximately optimum solution through the global search ability of genetic algorithm. When using genetic algorithm to solve the parallel machine preemptive scheduling problem, chromosome information becomes very complicated with different lengths. Therefore, by redesigning chromosome representation, this study can effectively solve this problem.
For the verification and comparison, we did an experiment based on two different job parameter patterns, regular and irregular, for the comparison of traditional SRPT method. The result shows, when the job parameter is regular, CPGA proposed in this study can have the optimal solution the same as SRPT. When the job parameter is irregular, we use the job case randomly chosen according to the size of jobs and the tightness of job scheduling time to do the experiment. The result shows CPGA can have a better solution for medium and small problems, and will not violate the deadline constraint. However, in the case of big problems, it is not as good as SRPT. Therefore, we can have the conclusion that the methodology proposed in this study can really solve multiple constraints parallel machine preemptive scheduling problem.

並列關鍵字

Constraint programming ； Genetic algorithm ； Parallel machine ； Preemptive scheduling

參考文獻

[1] Allahverdi, A, and Mittenthal, J., 1994. Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time. Naval Research Logistics 41, 677-682.

[2] Azizoglu, M., 2003. preemptive scheduling on identical parallel machines subject to deadlines. European Journal of Operational Research, 148, 205-210.

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

[5] Brailsford, S.C., Potts, C.N. and Smith B.M., 1999. Constraint satisfaction problems:Algorithms and applications. European Journal of Operational Research 119,557-581.

makespan. Policy and Information, vol.9, No.2, December.