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

Scheduling Two-Stage Hybrid Flow Shop with Availability Constraints

本研究考量雙階段混合型流程工廠之排程問題，第一階段僅有一部機器，第二階段有兩部機器，且機器都有使用限制。機器在完成特定工作個數後，必須進行預防維修或調整，為求機器的使用率極大化，發展SJL與LJL 兩個啟發式演算法，使總完工時間最小化。兩個演算法複雜度皆為O（n2 ），先應用 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 schedulingproblem with machine availability. The scheduling model only involvedone machine at the first stage and two machines at the second stage. Theobjective is minimizing makespan. In this paper, the machine must bemaintained or adjusted (machine unavailability) after the machine finishesa given number of jobs. This paper has developed two constructiveheuristics which are SJL and LJL algorithms with O(n2) time-complexities.Both algorithms applied the longest processing time (LPT) rule, andrespectively applied S-shape jobs assignment and balancing loading rule instage 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 thanAllaoui 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 relativeperformance is only 1.09%. The LJL algorithm obtained the LB in 783,the percentage for obtaining the LB is 48.94%, and the mean relativeperformance is 1.09%. The proposed SJL and LJL algorithms performedsignificantly effectively.