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

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

10.29977/JCIIE.200803.0002

M. B. Fakhrzad；Mehdi Heydari

混合式流程工作排程 ； 提早及遲延成本批量 ； 瓶頸資源 ； 資源平準化 ； hybrid flow-shop ； earliness and tardiness ； bottleneck resources ； resource leveling

工業工程學刊

25卷2期（2008 / 03 / 01）

105 - 115

英文

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

1. Aarts, E.,J. K. Lenstra(1997).Search in Combinatorial Optimization.New York:Wiley.
2. 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.
3. 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.
4. 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.
5. 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.
6. Braha, S. A.,L. L. Loob(1999).Heuristics for scheduling in a flow-shop with multiple processors.European Journal of Operational Research,13,113-122.
7. Chang, J.,W. Yan,H. Shao(2004).Scheduling a twostage no wait hybrid flowshop with separated setup and removal times.Proceedings of the American Control Conference,Boston, MA, United States:
8. Chen, B.(1995).Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage.Journal of Operation Research Society,46,234-244.
9. Elmaghraby S. E.,R. E. Karnub(1995).OR Report No. 305.USA:OR & IE Dept. North Carolina State University.
10. Glover, F.(1989).Tabu search. Part I.ORSA Journal on Computing,1,190-206.
11. Glover, F.(1986).Future paths for integer programming and links to artificial intelligence.Computers and Operations Research,5,533-549.
12. Glover, F.(1990).Tabu search. Part II.ORSA Journal on Computing,2,4-32.
13. Gupta, J. N. D.(1988).Two-stage hybrid flow-shop scheduling problem.Journal of Operation Research Society,39,359-364.
14. Haouari, M.,R. M`Hallah(1997).Heuristics algorithms for the two-stage hybrid flowshop problems.Operation Research Letters,21,43-53.
15. Hoogeveen, J.,J. K. Lenestra,B. Veltman(1996).Preemptive scheduling in a two-stage multiprocessor flow-shop is NP-hard.European Journal of Operational Research,89,172-175.
16. Huang, W.,S. Li(1998).A two-stage hybrid flowshop with uniform machines and setup times.Mathematical and Computer Modeling,27,27-45.
17. Janiak, A.,M. Lichtenstein(2000).Comparison of some heuristic algorithms for the flow-shop problem with parallel machines to minimize the total earliness, tardiness and waiting time.Proceedings of the symposium, OR 2000,Dresden, Germany:
18. Kurz, M. E.,R. G. Askin(2004).Scheduling flexible flow lines with sequencing-dependent setup times.European Journal of Operational Research,159,66-82.
19. Kurz, M. E.,R. G. Askin(2003).Comparing scheduling rules for flexible flow lines.International Journal of Production Economics,85,371-388.
20. Kyparisis, G. J.,C. Koulamas(2001).A note on weighted completion time minimization in a flexible flow-shop.Operation Research Letters,29,5-11.
21. Lin, H. T.,C. J. Liao(2003).A case study in a two-stage hybrid flow-shop with setup time and dedicated machines.International Journal of Production Economics,86,133-143.
22. Liu, C. Y.,S. C. Chang(2000).Scheduling flexible flow shops with sequence-dependent setup effects.IEEE Transactions on Robotics and Automation,16,408-419.
23. Logendran, R.,S. Carson,E. Hanson(2005).Group scheduling in flexible flow shops.International Journal of Production Economics,96,143-155.
24. Pugazhendhi, S.,S. Thiagarajan,C. Rajendran,N. Anantharaman(2004).Generating non-permutation schedules in flowline based manufacturing systems with sequence-dependent setup times of jobs: A heuristic approach.The International Journal of Advanced Manufacturing Technology,23,64-78.
25. Ruiz, R.,C. Maroto(2006).A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility.European Journal of Operational Research,169,781-800.
26. Ruiz, R.,F. Sivrikaya-Serifoglu,T. Urlings(2006).Technical ReportTechnical Report,Spain:Polytechnic University of Valencia, Dept. of Applied Statistics and Operations Research.
27. Ruiz, R.,F. Sivrikaya-Serifoglu,T. Urlings(2008).Modeling realistic hybrid flexible flowshop scheduling problems.Computers and Operations Research,34,1151-1175.
28. Tian, P.,J. Ma,D. M. Zhang(1999).Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property: an investigation of generation mechanism.European Journal of Operational Research,118,81-94.
29. Vob. S.,A. Witt(2007).Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application.International Journal of Production Economics,105,445-458.

1. (2019).A meta-heuristic based on the Imperialist Competitive Algorithm (ICA) for solving Hybrid Flow Shop (HFS) scheduling problem with unrelated parallel machines.工業工程學刊,36(6),7-12.