機器使用限制下雙階段混合型流程工廠之排程

本研究考量雙階段混合型流程工廠之排程問題，第一階段僅有一部機器，第二階段有兩部機器，且機器都有使用限制。機器在完成特定工作個數後，必須進行預防維修或調整，爲求機器的使用率極大化，發展SJL與LJL兩個啟發式演算法，使總完工時間最小化。兩個演算法複雜度皆爲O(n^2)，先應用LPT法則，然後，分別以S指派與負荷平衡準則，使第二階段機器負荷接近平衡，再使用詹森法則與最後忙碌機器法則，排定各機器上之工作序列，最後，將第二階段上兩部機器的工作，進行移動或對調，降低等待時間。實驗結果顯示：SJL與LJL演算績效比H佳，在較大工作數時特別顯著。1600個例子中，SJL有735個等於LB，占45.94%，平均誤差爲1.09%；LJL有783個等於LB，占48.94%，平均誤差爲1.09%，顯示SJL與LJL具有良好的演算品質。

關鍵字

雙階段混合型流程工廠；機器使用限制；最大完工時間；啓發式演算法

並列摘要

This paper has dealt with the two-stage hybrid flowshop scheduling problem with machine availability. The scheduling model only involved one machine at the first stage and two machines at the second stage. The objective is minimizing makespan. In this paper, the machine must be maintained or adjusted (machine unavailability) after the machine finishes a given number of jobs. This paper has developed two constructive heuristics which are SJL and LJL algorithms with O(n^2) time-complexities. Both algorithms applied the longest processing time (LPT) rule, and respectively applied S-shape jobs assignment and balancing loading rule in stage 2, and then combined Johnson’s rule (JR) and the last busy machine (LBM) rule to produce a job sequence. Based on 1600 instances, computational results showed that SJL and LJL algorithms were better than llaoui and Artiba's H heuristic. The SJL algorithm obtained the LB in 735, the percentage for obtaining the LB is 45.94%, and the mean relative performance is only 1.09%. The LJL algorithm obtained the LB in 783, the percentage for obtaining the LB is 48.94%, and the mean relative performance is 1.09%. The proposed SJL and LJL algorithms performed significantly effectively.

並列關鍵字

two-stage hybrid flowshop ； machine availability ； makespan ； heuristic

國際替代計量

機器使用限制下雙階段混合型流程工廠之排程

全文下載

主題瀏覽