A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 3 Issue 3
Jul.  2016

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2016  >  3(3): 235-246
Ling Wang, Shengyao Wang and Xiaolong Zheng, "A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times," IEEE/CAA J. of Autom. Sinica, vol. 3, no. 3, pp. 235-246, 2016.
Citation: Ling Wang, Shengyao Wang and Xiaolong Zheng, "A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times," IEEE/CAA J. of Autom. Sinica, vol. 3, no. 3, pp. 235-246, 2016.
shu

A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times

  • Department of Automation, Tsinghua University, Beijing 100084, China

Funds:

This work was supported by the National Science Fund for Distinguished Young Scholars of China (61525304).

    Abstract
  • A hybrid estimation of distribution algorithm (EDA) with iterated greedy (IG) search (EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times (UPMSP-SDST). For makespan criterion, some properties about neighborhood search operators to avoid invalid search are derived. A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region. Two types of deconstruction and reconstruction as well as an IG search are designed in the IG-based exploitation phase. Computational complexity of the algorithm is analyzed, and the effect of parameters is investigated by using the Taguchi method of design-of-experiment. Numerical tests on 1640 benchmark instances are carried out. The results and comparisons demonstrate the effectiveness of the EDA-IG. Especially, the bestknown solutions of 531 instances are updated. In addition, the effectiveness of the properties is also demonstrated by numerical comparisons.

     

    • FullText(HTML)
  • loading
    • References(28)
  • [1]
    Cheng T C E, Sin C C S. A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research, 1990, 47(3): 271-292
    [2]
    Chen J, Pan Q K, Wang L, Li J Q. A hybrid dynamic harmony search algorithm for identical parallel machines scheduling. Engineering Optimization, 2012, 44(2): 209-224
    [3]
    Xu Y, Wang L, Wang S Y, Liu M. An effective shuffled frog-leaping algorithm for solving the hybrid flow-shop scheduling problem with identical parallel machines. Engineering Optimization, 2013, 45(12): 1409-1430
    [4]
    Lin S W, Ying K C. A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems. International Journal of Production Research, 2015, 53(4): 1065-1076
    [5]
    Mellouli R, Sadfi C, Chu C B, Kacem I. Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times. European Journal of Operational Research, 2009, 197(3): 1150-1165
    [6]
    Xu X Q, Lin J, Cui W T. Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data. International Journal of Production Research, 2014, 52(19): 5611-5625
    [7]
    Fanjul-Peyro L, Ruiz R. Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 2010, 207(1): 55-69
    [8]
    Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco, USA.: W.H. Freeman & Co., 1979.
    [9]
    Allahverdi A, Ng C T, Cheng T C E, Kovalyov M Y. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 2008, 187(3): 985-1032
    [10]
    Vallada E, Ruiz R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 2011, 211(3): 612-622
    [11]
    Behnamian J, Zandieh M, Fatemi Ghomi S M T. Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications, 2009, 36(6): 9637-9644
    [12]
    Chang P C, Chen S H. Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times. Applied Soft Computing, 2011, 11(1): 1263-1274
    [13]
    Fleszar K, Charalambous C, Hindi K S. A variable neighborhood descent heuristic for the problem of makespan minimisation on unrelated parallel machines with setup times. Journal of Intelligent Manufacturing, 2012, 23(5): 1949-1958
    [14]
    Lin S W, Ying K C. ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times. Computers & Operations Research, 2014, 51: 172-181
    [15]
    Yilmaz E D, Ozmutlu H C, Ozmutlu S. Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times. International Journal of Production Research, 2014, 52(19): 5841-5856
    [16]
    Arnaout J P, Rabadi G, Musa R. A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times. Journal of Intelligent Manufacturing, 2010, 21(6): 693-701
    [17]
    Avalos-Rosales O, Angel-Bello F, Alvarez A. Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. The International Journal of Advanced Manufacturing Technology, 2015, 76(9-12): 1705-1718
    [18]
    Chen J F. Scheduling on unrelated parallel machines with sequenceand machine-dependent setup times and due-date constraints. The International Journal of Advanced Manufacturing Technology, 2009, 44(11-12): 1204-1212
    [19]
    Lin S W, Lu C C, Ying K C. Minimization of total tardiness on unrelated parallel machines with sequence-and machine-dependent setup times under due date constraints. The International Journal of Advanced Manufacturing Technology, 2011, 53(1-4): 353-361
    [20]
    Hsu C J, Kuo W H, Yang D L. Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects. Applied Mathematical Modelling, 2011, 35(3): 1492-1496
    [21]
    Kuo W H, Hsu C J, Yang D L. Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects. Computers & Industrial Engineering, 2011, 61(1): 179-183
    [22]
    Joo C M, Kim B S. Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability. Computers & Industrial Engineering, 2015, 85: 102-109
    [23]
    Chen C L, Chen C L. Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology, 2009, 43(1-2): 161-169
    [24]
    Larrañaga P, Lozano J A. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. US: Springer, 2002.
    [25]
    Ceberio J, Irurozki E, Mendiburu A, Lozano J A. A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems. Progress in Artificial Intelligence, 2012, 1(1): 103-117
    [26]
    Ruiz R, StÄutzle T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 2007, 177(3): 2033-2049
    [27]
    Guinet A. Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria. International Journal of Production Research, 1993, 31(7): 1579-1594
    [28]
    Montgomery D C. Design and Analysis of Experiments (Seventh Edition) . New York, U. S. A.: John Wiley & Sons, 2008.
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1209) PDF downloads(19) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return