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

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

蘇玲慧(Ling-Huey Su) ； 廖俊景(Chun-Ching Liao)

《中原學報》 31卷3期 (2003/09) Pp. 197-209

https://doi.org/10.6358/JCYU.200309.0197

摘要

本論文探討包含單機與批次機台之三階段流程型工廠排程問題，係Ahmadi於1992年所提問題的延伸。Ahmadi所探討的是第二階段爲批次機台而第一及第三階段為單機機台之三階段排程問題。本論文探討其他兩種不同之類型，即批次機台分別在第一及第三階段之三階段排程問題，目標爲最小化總完成時間。兩者皆為NP-艱難問題，故針對兩種情況各提出－啓發式排程演算法與數學規劃模式。文中亦針對問題提出一些特性與定理，並將之用於啓發式排程演算法與數學規劃模式中。實驗結果顯示啓發式排程演算法的求解品質極佳。

關鍵字

排程 ； 三階段流程型工廠 ； 批次處理 ； 啓發式方法

並列摘要

This paper is an extension of a three-stage flowshop with a batch processor in the second stage and discrete processors in the first and the third stage studied by Ahmadi et al.[3].We consider two variants where the batch processor is located in the first and third stage respectively. The objective is to minimize the makespan. An efficient heuristic and a mathematical programming model for each case are presented. We prove some properties that identify a specific class of optimal schedule, and then use these properties in designing heuristics and the mathematical programming models. Computational experiences with the algorithms are also reported.

並列關鍵字

Scheduling ； Three-stage flowshop ； Batch processor ； Heuristic