skip to main content
10.1145/1276958.1277076acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
Article

An estimation of distribution algorithm with guided mutation for a complex flow shop scheduling problem

Published: 07 July 2007 Publication History

Abstract

An Estimation of Distribution Algorithm (EDA) is proposed toapproach the Hybrid Flow Shop with Sequence Dependent Setup Times and Uniform Machines in parallel (HFS-SDST-UM) problem. The latter motivated by the needs of a real world company. The proposed EDA implements a fairly new mechanism to improve the search of more traditional EDAs. This is the Guided Mutation (GM). EDA-GM generates new solutions by using the information from a probability model, as all EDAs, and the local information from a good known solution. The approach is tested on several instances of HFS-SDST-UM and compared with adaptations of meta-heuristics designed for very similarproblems. Encouraging results are reported.

References

[1]
L. Adler, N. Fraiman, E. Kobacker, M. Pinedo, J. C. Plotnicoff, and T. P. Wu. BPSS: A scheduling support system for the packaging industry. Operations Research, 41:641--648, 1993.
[2]
S. A. Brah. Scheduling in a Flow Shop with Multiple Processors. PhD thesis, University of Houston, 1988.
[3]
J. Cheng, Y. Karuno, and H. Kise. A shiting bottleneck approach for a parallel-machine flow shop scheduling problem. Journal of the Operations Research Society of Japan, 44:140--156, 2001.
[4]
R. R. García and C. Maroto. A genetic algorithm for hybrid flow shops with sequence dependent setup times and machine elegibility. European Journal of Operational Research, 169:781--800, 2006.
[5]
F. Glover and M. Laguna. Tabu Search. Kluwer, 1997.
[6]
J. N. D. Gupta. Two-stage hybrid flow shop scheduling problem. Operational Research Society, 39:359--364, 1988.
[7]
J. N. D. Gupta. Heuristics for hybrid flow shops with controllable processing times and assignable due dates. Computers and Operations Research, 29:1417--1439, 2002.
[8]
M. E. Kurz and R. G. Askin. Comparing scheduling rules for exible ow lines. International Journal of Production Economics, 85:371--388, 2003.
[9]
M. E. Kurz and R. G. Askin. Scheduling flexible flow lines with sequence dependent set-up times. European Journal of Operational Research, 159:66--82, 2003.
[10]
M. E. Kurz, M. Runkle, and S. Pehlivan. Comparing problem-based-search and random keys genetic algorithms for the SDST FFL makespan scheduling problem. working paper, 2005.
[11]
P. Larrañaga and J. A. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2001.
[12]
V. J. Leon and B. Ramamoorthy. An adaptable problem space based search method for flexible flow line scheduling. IIE Transactions, 29:115--125, 1997.
[13]
R. Linn and W. Zhang. Hybrid flow shop scheduling: A survey. Computers & Industrial Engineering, 37:57--61, 1999.
[14]
H. Mühlenbein and G. Paass. From recombination of genes to the estimation of distributions i. binary parameters. In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, Lecture Notes In Computer Science, Vol. 1141, pages 178--187. Springer-Verlag, 1996.
[15]
C. Oguz and M. F. Ercan. A genetic algorithm for hybrid flow shop scheduling with multiprocessor tasks. Journal of Scheduling, 8:323--351, 2005.
[16]
M. Pinedo. Scheduling Theory, Algorithms and Systems. Prentice Hall, 2002.
[17]
J. A. V. Rodríguez. Meta-hyper-heuristics for hybrid flow shops. Ph.D. thesis, University of Essex, 2007.
[18]
J. A. V. Rodríguez and A. Salhi. Performance of single stage representation genetic algorithms in scheduling exible ow shops. In Congress on Evolutionary Computation (CEC2005), pages 1364--1371. IEEE Press, 2005.
[19]
D. L. Santos, J. L. Hunssucker, and D. E. Deal. FLOWMULT: Permutation sequences for flow shops with multiple processors. Journal of Information and Optimization Sciences, 16:351--366, 1995.
[20]
F. S. Serifoglu and G. Ulusoy. Multiprocessor task scheduling in multistage hybrid flow shops: A genetic algorithm approach. Journal of the Operational Research Society, 55:504--512, 2004.
[21]
H. W. Thornton and J. L. Hunsucker. A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage. European Journal of Operational Research, 152:96--114, 2004.
[22]
H. Wang. Flexible flow shop scheduling: Optimum, heuristics and artifical intelligence solutions. Expert Systems, 22:78--85, 2005.
[23]
B. Wardono and Y. Fathi. A tabu search algorithm for the multi-stage parallel machines problem with limited buffer capacities. European Journal of Operational Research, 155:380--401, 2004.
[24]
R. J. Wittrock. An adaptable scheduling algorithm for flexible flow lines. Operations Research, 36:445--453, 1988.
[25]
Q. Zhang, J. Sun, and E. Tsang. An evolutionary algorithm with the guided mutation for the maximum clique problem. IEEE Transactions on Evolutionary Computation, 9:192--201, 2005.
[26]
Q. Zhang, J. Sun, E. Tsang, and J. Ford. Estimation of distribution algorithm with 2-opt local search for the quadratic assignment problem. In J. Lozano, P. Larrañaga, I. Inza, and E. Bengoetxea, editors, Towards a New Evolutionary Computation. Advances in Estimation of Distribution Algorithm, pages 281--292. Springer-Verlag, 2006.

Cited By

View all
  • (2023)A Heuristic-Based Adaptive Iterated Greedy Algorithm for Lot-Streaming Hybrid Flow Shop Scheduling Problem with Consistent and Intermingled Sub-LotsSensors10.3390/s2305280823:5(2808)Online publication date: 3-Mar-2023
  • (2023)An improved estimation of distribution algorithm for rescue task emergency scheduling considering stochastic deterioration of the injuredComplex & Intelligent Systems10.1007/s40747-023-01136-x10:1(413-434)Online publication date: 25-Jul-2023
  • (2023)Hyper-heuristic Estimation of Distribution Algorithm for Green Hybrid Flow-Shop Scheduling and Transportation Integrated Optimization ProblemAdvanced Intelligent Computing Technology and Applications10.1007/978-981-99-4755-3_18(206-217)Online publication date: 30-Jul-2023
  • Show More Cited By

Index Terms

  1. An estimation of distribution algorithm with guided mutation for a complex flow shop scheduling problem

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation
    July 2007
    2313 pages
    ISBN:9781595936974
    DOI:10.1145/1276958
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 07 July 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. combinatorial optimization
    2. metaheuristics
    3. timetabling and scheduling

    Qualifiers

    • Article

    Conference

    GECCO07
    Sponsor:

    Acceptance Rates

    GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;
    Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)3
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 22 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)A Heuristic-Based Adaptive Iterated Greedy Algorithm for Lot-Streaming Hybrid Flow Shop Scheduling Problem with Consistent and Intermingled Sub-LotsSensors10.3390/s2305280823:5(2808)Online publication date: 3-Mar-2023
    • (2023)An improved estimation of distribution algorithm for rescue task emergency scheduling considering stochastic deterioration of the injuredComplex & Intelligent Systems10.1007/s40747-023-01136-x10:1(413-434)Online publication date: 25-Jul-2023
    • (2023)Hyper-heuristic Estimation of Distribution Algorithm for Green Hybrid Flow-Shop Scheduling and Transportation Integrated Optimization ProblemAdvanced Intelligent Computing Technology and Applications10.1007/978-981-99-4755-3_18(206-217)Online publication date: 30-Jul-2023
    • (2019)A Pareto-Based Estimation of Distribution Algorithm for Solving Multiobjective Distributed No-Wait Flow-Shop Scheduling Problem With Sequence-Dependent Setup TimeIEEE Transactions on Automation Science and Engineering10.1109/TASE.2018.288630316:3(1344-1360)Online publication date: Jul-2019
    • (2018)Applied Research on Distributed Generation Optimal Allocation Based on Improved Estimation of Distribution AlgorithmEnergies10.3390/en1109236311:9(2363)Online publication date: 7-Sep-2018
    • (2018)Convergence analysis of the plant propagation algorithm for continuous global optimizationRAIRO - Operations Research10.1051/ro/201703752:2(429-438)Online publication date: 22-Jun-2018
    • (2018)An Evolutionary Algorithm Based Hyper-heuristic for the Job-Shop Scheduling Problem with No-Wait ConstraintHarmony Search and Nature Inspired Optimization Algorithms10.1007/978-981-13-0761-4_25(249-257)Online publication date: 24-Aug-2018
    • (2017)Hybrid evolutionary approaches for the single machine order acceptance and scheduling problemApplied Soft Computing10.1016/j.asoc.2016.09.05152:C(725-747)Online publication date: 1-Mar-2017
    • (2015)Generating Easy and Hard Problems using the Proximate Optimality PrincipleProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2764890(767-768)Online publication date: 11-Jul-2015
    • (2014)A modified RBM-based estimation of distribution algorithm for steelmaking-continuous casting schedulingProceeding of the 11th World Congress on Intelligent Control and Automation10.1109/WCICA.2014.7052999(1836-1841)Online publication date: Jun-2014
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media