以組合派工法則求解雙流線型工廠排程

Abstract

本論文主要研究一個允許跨廠製造之雙流線型工廠(Dual Flow Shop)排程問題。排程目標為最小化寬裕度的變異係數。所謂的寬裕度，指的是交期與總加工時間之差距。此排程問題包含兩項排程決策：加工途程( Route Assignment, 指派工件到各站)與工件排序( Job Sequencing )。本研究發展一套可同時求解加工途程與加工順序之基因演算法(GA)，而在加工順序方面更使用了多種派工法，讓基因演算法更具多樣性。這些派工法包括單一啟發式演算法、組合派工法以及演化式之派工法則。針對這幾種演算法，本研究皆透過實驗，進行數據間的比較。 實驗結果指出在各種情境下，上述三種方法中，並沒有一種派工法能顯著的贏過其他績效。但是，在大部分的情境下，組合派工法皆能提供相對穩健與較佳之績效結果。

This research investigates a dual flow shop scheduling problem, which is in the context of allowing cross-shop processing. The scheduling objective is to minimize the coefficient of variation of slack time, in which the slack time of a job denotes the difference between its due date and total processing time. This scheduling problem involves two decisions: route assignment (assigning jobs to shops) and job sequencing. We developed a genetic algorithm (GA) for making the route assignment decision, which is further varied by including various kinds of dispatching algorithms. These dispatching algorithms include single heuristic rules, combined dispatching rules, and evolutionary approach. Numeric experiments for comparing these scheduling algorithms are carried out. Experiment results indicate that none of the GAs could outperform the others in all scenarios. Yet, the GA equipped with the combined dispatching rules is relatively more robust, performing quite well in most scenarios.