最小化訂單總完工時間之平行機台排程問題

Order Scheduling with Total Order Completion Time on Non-Identical Parallel Machines

范振晃(Jhen-Huang Fan)

指導教授 ： 許錫美 ； 洪暉智

國立交通大學/管理學院/工業工程與管理系所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00256

摘要

本研究探討在多部彈性之非相同平行機台下，最小化訂單總完工時間之訂單排程問題。研究目的為找出訂單中工件的最佳指派使得訂單總完工時間最小。我們驗證了兩項最佳解性質，把決策拆成兩階段並藉此建構了四個近似最佳解的演算法。在模擬實驗中我們驗證本研究所提出的演算法的有效性，並找出幾個影響演算法績效的因素。

關鍵字

訂單排程 ； 平行機台 ； 彈性機台 ； 總完工時間

並列摘要

We study the order scheduling problem under the non-identical parallel machines environment in the fully flexible case. Our goal is to minimize total order completion time and the decision is to assign all jobs to all machines. We first show two lemmas for optimal solution and separate our problem into two stages based on these lemmas. Then, we develop a series of two-stage heuristics to solve our problem. Finally, we implement numerical studies to verify the performance of our heuristics, and find out several factors that influence the performance of heuristics.

並列關鍵字

Order scheduling ； unrelated parallel machines ； fully flexible machines ； total order completion time

參考文獻

Blocher, J. and Chhajed, D., 1996. The customer order lead-time problem on parallel

Coffman, E.G., Garey, M.R. and Johnson, D.S., 1978. An application of bin-packing

Dell’Amico M. and Martello S., 1995. Optimal scheduling of tasks on identical

Theory of NP-Completeness. San Francisco: Freeman.

Graham, R.L., 1969. Boundaries on multiprocessing timing anomalies. SIAM