單機與雙機之動態排程

Study on Single-machine and Two-machine Problems in the Dynamic Scheduling Environment

李銓恩(chiuan-en li)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2001年)

https://doi.org/10.6840/cycu200100141

摘要

本研究將針對兩種不同的動態排程問題加以探討。一為最小化總延遲工作加權權重的單機排程問題(1 | | )。另一情況為雙機流程型工廠最小化所有工作完成時間(total flow time)與總流程時間(makespan)，並加以考慮不等待以及發生阻礙的限制條件。
在單機動態排程的問題中，建構一具有 個變數與9N條限制式的整數規劃模式。此外由於此問題屬於NP-complete的問題，所以提出一啟發式演算法來改善求解。此啟發式方法平均求解品質高達98%以上。而求解時間方面，即使處理100個工作件的問題也僅需要0.0165秒的求解時間。本方法可求取出近似最佳解甚至於最佳解。就我們所知，本研究是第一個利用啟發式方法針對1 | | 此問題加以求解的。
在雙機流程型工廠的問題中，首先利用將時間凍結的方法，將動態排程問題簡化為靜態的的模式。並建構一具有 個變數以及9N條限制式的整數規劃模式。已知此一問題屬於NP-complete的問題，本研究中提出一複雜度為 的啟發式演算法，並利用一判斷指標作為本啟發式方法的基礎。而由實驗結果分析得知，本啟發式方法能夠有效的求取出排程順序解，其中平均求解品質高達96.74%。而針對工作數為14的實驗樣本，平均求解時間僅需要0.000248秒。並由結果得知本研究可求取近似最佳解甚至最佳解。

關鍵字

權重 ； 不等待 ； 排程 ； 動態 ； 阻礙

並列摘要

This paper consider two different dynamic scheduling models. First, minimization of weighted number of tardy jobs on a single machine (1 | | ). Second, minimization of total flow time and makespan on two machine flowshop wherein both no-wait and blocking in process are considered.
In the first case, an integer programming model with variables and 9N constraints is formulated. A heuristic is then presented to solve this NP-complete problem. The average solution quality of the heuristic algorithm is about 98%. A 100 job case requires only 0.0165s, on average, to obtain a near or even optimal solution. To the best of our knowledge, this is the first heuristic approach that attempts to solve the 1 | | problem.
In the second case, a frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. An integer programming model with variables and 9N constrains, is formulated. Since the problem is known to be NP-complete, a heuristic algorithm with the complexity of is provided. A decision index is developed as the basic for the heuristic. Experimental results show that the proposed heuristic algorithm is efficient. The average solution quality of the heuristic algorithm is above 96.74%. A 14-job case requires only 0.000248s, on average, to obtain a near or even optimal solution.

並列關鍵字

scheduling ； weighted ； dynamic ； blocking ； no-wait

參考文獻

1. Akturk, M.S. and Ozdemir, D., (2000) An exact approach to minimizing total weighted tardiness with release dates. IIE Transactions 32, 1091-1101.

2. Aldowaisan, T. and Allahverdi, A. (1998) Total flowtime in no-wait flowshops with separated setup times. Computers Operations Research, 25 (9), 757-765.

3. Allahverdi, A. (1997) Scheduling in stochastic flowshops with independent setup, processing and removal times. Computers and Operations Research 24(10), 955-960.

4. Allahverdi, A. and Aldowaisan, T. (2000) No-wait and separate setup three-machine flowshop with total completion time criterion. International transactions in Operational Research, 7, 245-264.

5. Allahverdi, A. (2000) Minimizing mean flowtime in a two-machine flowshop with sequence independent setup times. Computers and Operations Research, 27, 111-127.