給定完工順序下允許中斷開放工廠排程問題之研究

Scheduling Preemptive Open Shops With A Given Job Completion Sequence

李政儒(Chang-Ju Lee)

指導教授 ： 廖經芳

朝陽科技大學/理工學院/工業工程與管理系/碩士(2010年)

摘要

排程問題本身屬於組合最佳化問題，許多研究證實大多數排程問題都為NP-hard問題，複雜度高且不易求解的問題。本研究探討給定完工順序下允許中斷開放工廠之排程問題，其中與以往不同的是工件完工的順序必須符合C1≦C2≦…≦Cn限制，並且允許工件在處理過程中可以任意中斷。本研究經由總完工時間(ΣCi)及總延遲時間(ΣTi)最小化問題之分析，證實工件的適度延後完工是對目標函數值有所助益的。針對總延遲工件數(ΣUi)最小化問題，本研究提出HEU_F和HEU_S兩種啟發式演算法來求得近似解，並利用一致性問題和非一致性問題來測試演算法之優劣。針對一致性之問題下，HEU_F演算法整體平均誤差百分比為3.07%，以及整體非最佳解之誤差比例為8.04%；HEU_S演算法整體平均誤差百分比為1.83%，以及整體非最佳解之誤差比例為0.70%。針對非一致性之問題下，HEU_S演算法整體平均誤差百分比為為24.65%，以及整體非最佳解之誤差比例為14.95%。

關鍵字

完工順序 ； 啟發式 ； 開放工廠 ； 完工時間 ； 延遲工件 ； 延遲時間

並列摘要

Most scheduling problems are NP-hard combinational optimization problems. That is, they are extremely complex and difficult to solve. In this thesis, the preemptive open shop scheduling problem with a given job completion sequence is investigated.
Without loss of generality, we assume that the jobs must be completed in the sequence C1≦C2≦…≦Cn. We first examine the problems with the objective of minimizing total completion time (ΣCi) and total tardiness (ΣTi). Both of them can be formulated as linear programs. It is shown that in some case the unforced delay of job completion may be helpful. In other words, it is not always advantageous to complete jobs as early as possible. Then, we develop two heuristics, HEU_F and HEU_S, for the problem whose objective is minimizing number of tardy jobs (ΣUi).
To evaluate the performance of the proposed heuristics, the solutions obtained are compared with optimal solutions from LINGO software. For consistent problems, heuristic HEU_F has an average relative percentage deviation of 3.07%. Also, only 8.04% of the tested instances are not optimally solved. On the other hand, heuristic HEU_S has an average relative percentage deviation of 1.83%, and only 0.70% of the tested instances are not optimally solved. For non-consistent problems, heuristic HEU_S perfroms worse. It has an average relative percentage deviation of 24.65%, and 14.95% of the tested instances are not optimally solved.

並列關鍵字

Completion time ； Given A job Completion Sequence ； Heuristic ； Open Shops ； Tardy Jobs ； Total Tardiness

參考文獻

Achugbue, J.O., and Chin F.Y., “Scheduling the open shop to minimize mean flow time”, SIAM J. COMPUT., Vol.11, pp.709-720, (1982).

Aksjonov.V.A. , “A polynomial-time algorithm of approximate solution of a scheduling problem”, Upravlyaemye Sistemy, Vol.28, pp.273-281,(1989).

Alidaee Bahrama, Duaneb Rosa, "Scheduling Parallel Machines To Minimize Total Weighted And Unweighted Tardiness", Computers & Operations Research, Vol. 24, No 8, pp.775-788,(1997).

Amaral Armentano, V. V., Rigao Scrich, C., "Tabu Search For Minimizing Total Tardiness In A Job Shop", International Journal Of Production Economics, Vol. 63, No. 2, pp.131-140,(2000).

Deman, V., John, M., and Baker, K.R., “Minimizing mean flow time in the flow shop with no intermediate queues”, AIIE Transactions, Vol.6, No.1, pp.28-34,(1974).