包含單機與批次機台三階段流程型工廠排程問題

Scheduling for a Three-Stage Flowshop with Batch and Discrete Processors

黃振周(Chen-Chou Huang)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2002年)

https://doi.org/10.6840/cycu200200385

摘要

本研究分為三個子題，旨在探討三階段流程型工廠在各階段各有一批次機台，而在其他兩階段則為單機機台之排程問題，批次機台可同時處理有限個數之工件，而一旦進行加工處理，工件不可從機台排入或移出。排程之衡量指標為工作總完成時間。對於批次機台位於第二階段之排程問題已被證明為NP-complete，本研究繼續擴展，並證明批次機台位於第一及第三階段之排程問題亦為NP-complete（附錄）。由於為NP-complete問題，因此本研究擬對於各子問題提出一啟發式排程演算法以縮短求解時間，並分別建立數學規劃模式以驗證啟發式排程演算法之求解品質。同時針對三個子問題，分別提出各問題之一些特性以使得不論是啟發式排程演算法或數學規劃模式皆更有效率。

關鍵字

批次型機台 ； 排程 ； 三機 ； 流程型工廠

並列摘要

This study considers the three-stage flowshop problem with batch processor at one stage and discrete processor at each of the other two stages. Each batch process can process a batch with limited number of jobs simultaneously. Once the process begins, no job can be released from the batch processor until the entire batch is processed. The performance measure is makespan. In this study, we analyze a class of three cases in which the batch processor plays an important role. For the problem in which the batch processor in the second stage has been proven to be NP-complete, we now extended the proof to the case in which the batch processor in the first stage and the third stage are scheduled so that the makespan is minimized. We proposed efficient heuristic procedures for each of the case to cope with realistic problems. A mathematical programming is presented for benchmarking. Several solution properties are characterized to incorporate into the heuristic procedure and mathematical programming model.

並列關鍵字

three-stage ； batch processor ； scheduling ； flowshop

參考文獻

2. Ahmadi, J.H., Ahmadi, R.H., Dasu, S. and Tang, C.S., 1992, “Batching and scheduling jobs on batch and discrete processors.” Operations Research 39 (4), 750-763.

3. Campbell, H.G., Dudek, R.A., Smith, M.L., 1970. ”An heuristic algorithm for n job m machine sequencing problem.” Management Science 16/B, 630-637.

4. Chandru, V., Lee C.Y. and Uzsoy, R. 1993 ’’Minimizing total completion time on batch processing machine.’’ International Journal of Production Research 31, 2097-2121.

5. Chang S. Suang, Young H.K., Sang H.Y., 2000 “A problem reduction and decomposition approach for scheduling for a flowshop of batch processing

6. Chang T.C.E. and Wang G.., 1998 “Batching and scheduling to minimize the makespan in the two-machine flowshop.’’ IIE Transactions 30, 447-453.