Flow Shop Scheduling with Shortening Jobs for Makespan Minimization

被引：1
作者：
Sun, Zheng-Wei [1 ]
Lv, Dan-Yang [2 ,3 ]
Wei, Cai-Min [4 ]
Wang, Ji-Bo [1 ]
机构：
[1] Shenyang Aerosp Univ, Sch Comp, Shenyang 110136, Peoples R China
[2] Shenyang Aerosp Univ, Sch Mechatron Engn, Shenyang 110136, Peoples R China
[3] Shenyang Aerosp Univ, Key Lab Rapid Dev & Mfg Technol Aircraft, Minist Educ, Shenyang 110136, Peoples R China
[4] Shantou Univ, Sch Math & Comp, Shantou 515063, Peoples R China
来源：
MATHEMATICS | 2025年 / 13卷 / 03期
关键词：
scheduling; flow shop; shortening job; makespan; branch-and-bound algorithm; heuristic algorithm; TOTAL COMPLETION-TIME; SOLUTION ALGORITHMS; DETERIORATING JOBS; COMPLEXITY;
D O I：
10.3390/math13030363
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
This paper deals with a two-machine flow shop problem with shortening jobs. A shortening job means that the job's processing time is a decreasing function of its starting time. The aim is to find a sequence that minimizes the makespan of all the jobs. several dominance properties, some lower bounds, and an initial upper bound are derived, which are applied to propose a branch-and-bound algorithm to solve the problem. We also propose some heuristics and mathematical programming. Computational experiments are conducted to evaluate the performance of the proposed algorithms.
引用
收藏
页数：23
相关论文
共 50 条
  • [41] Makespan minimization scheduling with ready times, group technology and shortening job processing times
    Wang, Ji-Bo
    Liu, Lu
    Wang, Jian-Jun
    Li, Lin
    [J]. COMPUTER JOURNAL, 2018, 61 (09) : 1422 - 1428
  • [42] Flow shop scheduling with jobs arriving at different times
    Li, Guo
    Li, Na
    Sambandam, Narayanasamy
    Sethi, Suresh P.
    Zhang, Faping
    [J]. INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2018, 206 : 250 - 260
  • [43] Exact distribution of the makespan in a two machines flow shop with two kinds of jobs
    Baptiste, P
    Jacquemard, C
    [J]. INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2001, 74 (1-3) : 77 - 83
  • [44] Application of Firefly Algorithm in Job Shop Scheduling Problem for Minimization of Makespan
    Udaiyakumar, K. C.
    Chandrasekaran, M.
    [J]. 12TH GLOBAL CONGRESS ON MANUFACTURING AND MANAGEMENT (GCMM - 2014), 2014, 97 : 1798 - 1807
  • [45] Makespan minimization for m-machine permutation flowshop scheduling problem with learning considerations
    Chung, Yu-Hsiang
    Tong, Lee-Ing
    [J]. INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2011, 56 (1-4) : 355 - 367
  • [46] A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time
    Baraz, Daniel
    Mosheiov, Gur
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 184 (02) : 810 - 813
  • [47] Shop scheduling problems with pliable jobs
    Knust, S.
    Shakhlevich, N., V
    Waldherr, S.
    Weiss, C.
    [J]. JOURNAL OF SCHEDULING, 2019, 22 (06) : 635 - 661
  • [48] Scheduling deteriorating jobs to minimize makespan
    Kubiak, W
    van de Velde, S
    [J]. NAVAL RESEARCH LOGISTICS, 1998, 45 (05) : 511 - 523
  • [49] Scheduling deteriorating jobs to minimize the makespan on a single machine
    Chin-Chia Wu
    Yau-Ren Shiau
    Ling-Huei Lee
    Wen-Chiung Lee
    [J]. The International Journal of Advanced Manufacturing Technology, 2009, 44 : 1230 - 1236
  • [50] Scheduling Deteriorating Jobs with Availability Constraints to Minimize the Makespan
    Zhao, Chuanli
    Tang, Hengyong
    [J]. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2016, 33 (06)
12345