等效平行機台在工件依批量到達下之最小總完工時間排程問題

Minimizing Total Flowtime with Arrival Time in Batches on Identical Parallel Machines

鍾翠萍(Tsui-Ping Chung)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200700416

摘要

本研究將針對等效平行機台在工件依批量到達情況下之排程問題加以探討，以最小總完工時間為目標。此問題已被證明為NP-hard問題，因此提出啟發式演算法並以分支界限法驗證。啟發式演算法先針對每一批量依SPT方法達到部分最佳化並利用BIP數學模式降低在每一個批量到達之間隔時間裡的空閒時間達到最小總完工時間之目標。實驗分成兩個部份由透過實驗測試得到啟發式演算法之求解品質誤差最多為6.7%。

關鍵字

等效平行機台 ； 到達時間 ； 分支界限法 ； 最小總完工時間

並列摘要

This paper considers the identical parallel machines problem, where jobs arrive in batches. The objective is to minimize the total completion time. Since the single machine problem with job arrival time is known to be NP-hard, therefore the problem is NP-hard in the strong sense. A heuristic procedure based on a Binary Integer Programming model to level the completion time of all jobs between two consecutive batch arrival times is developed to decrease the machine idle, which in turn minimize the total job completion time. A branch and bound algorithm is proposed for benchmarking. Computational results show that the solution quality error of the heuristic is at most 6.7%.

並列關鍵字

arrival time ； identical parallel machines ； total flow-time ； branch and bound algorithm

參考文獻

[1] Azizoglu, M., Kirca, O., 1999. On the minimization of total weighted flow time with identical and uniform parallel machines. European journal of operational research 113, 91-100

[2] Barnes, J.W.,Brennan, J.J., 1977.An improved algorithm for independent tasks to reduce mean finishing time. AIIE Transactions 17,382-387.

[3] Belouadeh, H.,Potts, C.N., 1994.Scheduling identical parallel machines to minimize total weighted completion time.Discrete Applied Mathematics 48, 201-218.

[4] Chu, C., 1992. A branch-and-bound algorithm to minimize total flow time with unequal release dates. Naval Research Logistics 39, 859-875.

[6] Du, J., Leung, J.Y-T., Young, G.H., 1991. Scheduling chain-structured tasks to minimize makespan and mean flow time. Information and Computation 92, 219-236.