雙機流程型工廠動態排程之研究

摘要

雙機流程型工廠排程問題中，決策者爲了達成提昇系統績效之目標，除了要使產出時間儘量降低之外，同時亦必須使在製品庫儲水準儘量降低，在這雙重考量因素要求下，本文將影響上述目標的主要兩項評估準則：(1)所有工作完成時間（makespan)最小化及(2)總流程時間(total flow time)最小化加總合併，使之成爲一個新的評估準則。並針對過去文獻較少探討而實際生產環境必須考慮的動態排程問題，提出一藉由凍結事件發生時間的方式，將動態排程問題轉化成爲一個靜態排程問題的解決方法。本文針對經轉化後的靜態排程問題提出一個N ² + 3N個變數與5N條限制式的整數規剡模式，並基於求解效率之考量，本文亦提出一個複雜度0(N ²)的啓發式排程演算法。經由實驗測試結果顯示，該啓發式排程演算法總平均的求解品質髙達96%以上，且15個工作的平均求解時間只需0.1483秒。反觀整數規劃模式平均求解時間至少需要1374秒以上，同時尙有近半數的實驗測試範例在可容許之求解時間下，無法獲得最佳解。因此，本文所提的啓發式排程演算法不論是在演算速度或求解品質上均具資際應用之價值。

Abstract

In this paper, we aim to solve a two-machine flowshop dynamic scheduling problem, in which the objective is to minimize the sum of makespan and total flow time. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N² + 4N variables and 6N constraints is formulated. In the consideration of computing time and complexity, a heuristic algorithm with the complexity of 0(N² ) is then presented. Experimental results show that the proposed heuristic algorithm can quickly solve this problem with very good solution quality. The average solution quality of the heuristic algorithm is above 96%. In a 15-job environment, it takes only 0.1483 seconds on average to obtain a ultimate solution. Compared with the integer programming model, the heuristic algorithm is much more practical to real world applications.

關鍵詞:

• 雙機流程型工廠
• 動態排程
• 靜態排程

Key Words:

• two-machine flowshop
• dynamic scheduling
• static scheduling