批量分割於零工型排程之影響分析

Effect Evaluation of Lot Splitting in Job Shop Scheduling

10.29977/JCIIE.200403.0009

駱景堯(Chin-Yao Low)；葉進儀(Jinn-Yi Yeh)；許瑞麟(Jui-Lin Hsu)

批量分割 ； 零工型生產 ； 瓶頸漂移法 ； 最大完工時間 ； 提早／延遲完工懲罰值 ； lot splitting ； job shop ； shifting bottleneck ； makespan ； early/tardiness penalties

工業工程學刊

21卷2期（2004 / 03 / 01）

193 - 202

繁體中文

在批量分割概念已被廣泛的運用於生產上藉以縮短總完工時間之同時，研究上大都以流程型生產系統之探討為主，至於在零工型生產系統之研究則寥寥可數。因此本研究旨在針對批量分割在零工型生產系統之應用作較為深入之探討，研究中並將每一作業具不可忽略之整備時間納入系統之考量。研究之進行分為兩階段，首先將問題在不分批之狀况下以在先關係圖描述之，而後發展以瓶頸漂移法為基之啓發式演算法進行求解以獲得所探討問題之初始解。隨後將各產品之生產量分為數個等子批，並以鄰點搜尋進行改善期獲得批量分割後之近似排程。為分析批量分割對於零工型生產環境之衝擊，本研究分別在最大完工時間最小化或提早/延遲完工懲罰値最小化之目標下以隨機產生之數據對於各種不同之問題規模及製程環境進行實驗分析。分析之結果顯示：將批量分割之觀念應用於零工型生產系統中可有效的縮短總完工時間或降低提早/延遲完工懲罰値，然而縮短之幅度以兩等批量分割之效益為最大，且隨著分割數之增加，縮短之幅度則逐漸趨緩。

As the lot splitting concept has been used widely to reduce the makespan in a productionsystem,most researches investigate the flow shop production systems and the job shopproduction systems have received much less attention relatively.This study investigatesthe application of lot splitting in a job shop production system with setup times whichcannot be omitted more thoroughly.The research is divided into two phases.First,Theaddressed job shop scheduling problem is illustrated by a disjunctive graph,then a shiftingbottleneck based heuristic is developed to solve the addressed scheduling problem withoutlot spitting.Following,each product is split into some consistent sublots,and aneighborhood searching procedure is then applied for finding a good solution.Two kindsof objectives that are minimizing makespan and early/tardiness penalties are evaluated.Inorder to investigate the influence of the number of sublots,due dates and setup times on ajob shop production system with regard to the corresponding objective considered,someexperiments are conducted.The experimental results shown that the lot splitting caneffectively reduce makespan and early/tardiness penalties in the job shop schedulingproblem.Two consistent sublots make the largest benefit,however,the benefits aregradually reduced with increasing the number of sublots.

1. Adams, J.,E. Balas,Zawacic, D.(1988).The shifting bottleneck procedure for job shop scheduling.Management Science,34(3),391-401.
2. Baker, K. R.,D. Jia(1993).A comparative study of lot streaming procedures.OMEGA,21(5),561-566.
3. Baker, K. R.,Pyke, D. F.(1990).Solution procedures for the lot streaming problem.Decision Science,21(3),475-491.
4. Balas, B.(1969).Machine sequencing via disjunctive graph: an implicit enumeration algorithm.Operations Research,17,1-10.
5. Balas, F.,J. K. Lenstra,A. Vazacopoulos(1995).One machine scheduling with delayed precedence constraints.Management Science,41,94-109.
6. Cetinkaya, F. C.,M. S. Kayaligil(1992).Unit sized transfer batch scheduling with setup time.Computers and Industrial Engineering,22(2),177-183.
7. Glass, C. A.,J. N. D. Gupta,C. N. Potts(1994).Lot streaming in three stage production processes.European Journal of Operational Research,75(2),378-394.
8. Graves, S. C.,M. M. Kostreva(1986).Overlapping operations in material requirements planning.Journal of Operations Management,6(3),283-294.
9. Hancock, T. M.(1991).Effects of lot-splitting under various routing strategies.International Journal of Operations and Production Management,11(1),68-75.
10. Jacobs, F. R.,D. J. Bragg(1988).Repetitive lots: flow time reductions through sequencing and dynamic batch sizing.Decision Science,19(2),281-294.
11. Karimi, I. A.(1992).Optimal cycle time in multistage serial system with setup and inventory cost.Management Science,38(10),1467-1481.
12. Kropp, D. H.,T. L. Smunt(1988).Optimal and heuristic models for lot-splitting in a flow shop.Decision Science,21(4),691-709.
13. Low, C.,T. H. Wu(2001).Mathematical modelling and heuristic approaches to operating scheduling problems in an fms environment.International Journal of Production Research,39(4),689-708.
14. Moily, J. P.(1986).Optimal and heuristic procedures for component lot-splitting in multistage manufacturing system.Management Science,32(1),113-125.
15. Pezzella, F.,E. Merelli(2000).A tabu search method guided by shifting bottleneck for the job shop scheduling problem.European Journal of Operational Research,120,297-310.
16. Stephane, D. P.,J. B. Lasserre(1993).An iterative procedure for lot-streaming in job shop scheduling.Computers and Industrial Engineering,25(1),231-234.
17. Sule, D. R.(1997).Industrial Scheduling.
18. Vickson, R. G.,B. F.,Alfredson(1992).Two and three machine flow shop scheduling problem with equal sized transfer batches.International Journal of Production Research,30(10),1551-1574.
19. Wanger, B. J.,G. L. Ragatz(1994).The impact of lot splitting on due date performance.Journal of Operations Management,12,13-25.
20. 邱煥能、向士中(1996)。流程型工廠單產品批量流最佳解與探索解模式之研究。工業工程學刊，13(1)，73-83。
21. 邱煥能、張仁輝(1996)。流程型工廠單產品批量流移運批量最佳配置探索解模式之研究。工業工程學刊，13(4)，329-341。
22. 駱景堯(1999)。零工型生產系統之批量流研究。工業工程學刊，16(6)，671-680。