A Heuristic Algorithm for Hybrid Flow-Shop Production Scheduling to Minimize the Sum of the Earliness Andf Tardiness Costs

啟發式演算法求解混合式流程生產排程之最小化總提早及遲延成本

M. B. Fakhrzad ； Mehdi Heydari

《工業工程學刊》 25卷2期 (2008/03) Pp. 105-115

https://doi.org/10.29977/JCIIE.200803.0002

摘要

本論文強調一種在每一階段（機器中心）具有平行機之流程式工作排程，求解最小化總提早及遲延成本之問題。評估準則為最小化維持及缺貨成本。本論文提出一個對混合式流程工作排程有效率的求解方式，三個啟發式演算法被發展出來並應用在這個問題。第一個演算法分派工件給機器，並將混合式流程工作排程轉換成數個流程工作排程問題。然後使用第二個演算法來求解一般的流程工作排程問題。第三個演算法會藉由剩餘有用資源來進行資源平準化。假如經過幾次迭代後之解答並沒有改進，則已達到停止條件。本研究的計算實驗結果顯示，本研究所提之求解方法可決定對有限資源（瓶頸）作最佳化運用的整數線性規劃問題，且比SA/TS演算法具有優越性。

關鍵字

混合式流程工作排程 ； 提早及遲延成本批量 ； 瓶頸資源 ； 資源平準化

並列摘要

This paper addresses a flow-shop scheduling problem with identical parallel machines at each stage (machine center) for minimizing the sum of the earliness and tardiness costs. The criteria are to minimize maintenance and shortage costs. An efficient solution approach for hybrid flow-shop scheduling problem is presented. Three heuristic algorithms are developed and utilized in this approach. The first algorithm allocates jobs to machines and converts the hybrid flow-shop problem in to several flow-shop problems. Then each ordinary flow-shop problem is solved utilizing a second algorithm. The third algorithm performs resource leveling by comparing the remaining utilized resources. If there's no improvement in the solution after several iterations, the stopping condition is reached. Computational experiments in this research determines the optimum utilization of the limited resources (bottlenecks) and their superiority over SA/TS algorithm is shown and establishes a solution method for integer linear programming problems.

並列關鍵字

hybrid flow-shop ； earliness and tardiness ； bottleneck resources ； resource leveling

參考文獻

Aarts, E.,J. K. Lenstra(1997).Search in Combinatorial Optimization.New York:Wiley.

Allaoui, H.,A. Artiba(2004).Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints.Computers and Industrial Engineering.47,431-450.

Andre´s, C.,J. M. Albarracı´n,G. Tormo,E. Vicens,J. P. Garcı´a-Sabater(2005).Group technology in a hybrid flowshop environment: A case study.European Journal of Operational Research.167,272-281.

Bertel. S.,J. C. Billaut(2004).A genetic algorithm for an industrial multiprocessor flow-shop scheduling problem with recirculation.European Journal of Operational Research.159,651-662.

Botta-Genoulaz, V.(2000).Hybrid flow-shop scheduling with precedence constrains and time legs to minimize maximum lateness.International Journal of Production Economics.64,101-111.