An effective two-stage heuristic for scheduling the distributed assembly flowshops with sequence dependent setup times

被引:0
|
作者
Song, Hong-Bo [1 ]
Lin, Jian [2 ]
Chen, You-Rong [1 ]
机构
[1] Zhejiang Shuren Univ, Coll Informat Sci & Technol, Hangzhou 310015, Peoples R China
[2] Zhejiang Univ Finance & Econ, Dept Artificial Intelligence, Hangzhou 310018, Peoples R China
基金
中国国家自然科学基金;
关键词
Distributed assembly flowshop scheduling; Two-stage heuristic algorithm; Neighborhood decent for critical-jobs-sequence; Sequence dependent setup times; APPROXIMATION SCHEME; ALGORITHM; MAKESPAN; SEARCH;
D O I
10.1016/j.cor.2024.106850
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This paper studies the Distributed Assembly Permutation Flowshop Scheduling Problem with Sequence Dependent Setup Times (DAPFSP-SDST). The optimization objective is minimization of maximal completion time (makespan), and it is shown that minimizing the sum of Total Setup Times for Assembling Products (TSTAP) and Total Idle Times on Assembly Machine (TITAM) is equivalent to minimizing the makespan. Additionally, minimization of TSTAP and TITAM can be transformed into sequencing problems of products and jobs within critical products, respectively. We also find out that a product sequence essentially explores an area in the solution space, with solutions in the area having the same TSTAP but different TITAMs determined by Critical-JobsSequences (CJSs). Based on the new findings, an effective Two-Stage Heuristic Algorithm (TSHA) is proposed to first obtain promising product sequences and then exploit the corresponding areas for the DAPFSP-SDST. At the first stage of TSHA, high-quality initial product sequences are obtained through a constructive method and two Neighborhood Descent for Product Sequence (NDPS) algorithms are presented for more potential searching areas. At the second stage, a Neighborhood Descent for CJS (NDCJS) is designed to find CJSs with TITAM as small as possible. Evaluations on a benchmark instance set show that TSHA achieves better performance compared to the existing meta-heuristic and hyper-heuristic algorithms on the DAPFSP-SDST. Another impressive advantage of the TSHA is its low computational cost, as it is a heuristic algorithm with some neighborhood search operators.
引用
收藏
页数:12
相关论文
共 50 条
  • [31] Scheduling for two-stage production system with setup and assembly operations
    Yokoyama, M
    COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (12) : 2063 - 2078
  • [32] General flowshop scheduling problem with the sequence dependent setup times: A heuristic approach
    Ziaee, Mohsen
    INFORMATION SCIENCES, 2013, 251 : 126 - 135
  • [33] A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times
    Franca, PM
    Gendreau, M
    Laporte, G
    Muller, FM
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 1996, 43 (2-3) : 79 - 89
  • [34] Uniform Parallel Machine Scheduling with Sequence Dependent Setup Times: A Randomized Heuristic
    Yildiz, Beste
    Kandiller, Levent
    Toy, Ayhan Ozgur
    DIGITIZING PRODUCTION SYSTEMS, ISPR2021, 2022, : 812 - 825
  • [35] A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times
    Gendreau, M
    Laporte, G
    Guimaraes, EM
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2001, 133 (01) : 183 - 189
  • [36] Simple constructive heuristics for the Distributed Assembly Permutation Flowshop Scheduling Problem with Sequence Dependent Setup Times
    Hatami, Sara
    Ruiz, Ruben
    Andres-Romano, Carlos
    2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), 2014, : 19 - 23
  • [37] A two-stage heuristic for disassembly scheduling with assembly product structure
    Lee, DH
    Xirouchakis, P
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2004, 55 (03) : 287 - 297
  • [38] Approximation Algorithms for Scheduling Multiple Two-Stage Flowshops
    Wu, Guangwei
    Wang, Jianxin
    COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 516 - 528
  • [39] On scheduling inclined jobs on multiple two-stage flowshops
    Wu, Guangwei
    Chen, Jianer
    Wang, Jianxin
    THEORETICAL COMPUTER SCIENCE, 2019, 786 : 67 - 77
  • [40] Scheduling a two-stage hybrid flow shop with dedicated machines, time lags and sequence-dependent family setup times
    Harbaoui, H.
    Bellenguez-Morineau, O.
    Khalfallah, S.
    2016 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC), 2016, : 2990 - 2995