Enhanced lower bounds and exact procedures for total completion time minimization in a two-machine permutation flowshop with release dates

被引：4
作者：
Mrad, Mehdi [1 ]
Chalghoumi, Sabrine [2 ]
Ladhari, Talel [2 ,3 ,4 ]
Gharbi, Anis [1 ]
机构：
[1] King Saud Univ, Dept Ind Engn, Riyadh, Saudi Arabia
[2] Univ Tunis, BADEM, Tunis 2059, Tunisia
[3] Univ Tunis, Ecole Super Sci Econ & Commerciales Tunis, 1089 Montfleury, Tunis, Tunisia
[4] Umm Al Qura Univ, Coll Business Management, Dept Business Adm, Mecca, Saudi Arabia
来源：
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH | 2019年 / 26卷 / 06期
关键词：
flowshop; total completion time; release date; lower bounds; mixed-integer linear programming; INTEGER PROGRAMMING FORMULATIONS; SHOP SCHEDULING PROBLEM; LOCAL SEARCH; ALGORITHM;
D O I：
10.1111/itor.12421
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider the problem of minimizing the sum of completion times in a two-machine permutation flowshop subject to release dates. New procedures are proposed for effectively bounding the completion time of a given job that is processed at a given position. New assignment-based lower bounds are derived as well as an enhanced mathematical programming formulation. Our computational analysis shows a consistent tightness of the proposed lower bounds and a high outperformance of the enhanced mathematical formulation with respect to the classical one.
引用
收藏
页码：2432 / 2449
页数：18
相关论文
共 37 条
[21]   Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues [J].
Juan, Angel A. ;
Lourenco, Helena R. ;
Mateo, Manuel ;
Luo, Rachel ;
Castella, Quim .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2014, 21 (01) :103-126
[22]   Mixed integer programming formulations for single machine scheduling problems [J].
Keha, Ahmet B. ;
Khowala, Ketan ;
Fowler, John W. .
COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 56 (01) :357-367
[23]   MIP models for minimizing total tardiness in a two-machine flow shop [J].
Kharbeche, M. ;
Haouari, M. .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2013, 64 (05) :690-707
[24]   A mixed integer programming approach for the single machine problem with unequal release dates [J].
Kooli, Anis ;
Serairi, Mehdi .
COMPUTERS & OPERATIONS RESEARCH, 2014, 51 :323-330
[25]   Heuristics and lower bounds for minimizing the total completion time in a two-machine flowshop [J].
Ladhari, Tale ;
Rakrouki, Mohamed Ali .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2009, 122 (02) :678-691
[26]   A Truncated Sum of Processing-Times-Based Learning Model for a Two-Machine Flowshop Scheduling Problem [J].
Lai, Kunjung ;
Hsu, Peng-Hsiang ;
Ting, Ping-Ho ;
Wu, Chin-Chia .
HUMAN FACTORS AND ERGONOMICS IN MANUFACTURING & SERVICE INDUSTRIES, 2014, 24 (02) :152-160
[27]   Minimizing the total completion time in a two-machine flowshop problem with time delays [J].
Msakni, Mohamed Kais ;
Khallouli, Wael ;
Al-Salem, Mohamed ;
Ladhari, Talel .
ENGINEERING OPTIMIZATION, 2016, 48 (07) :1164-1181
[28]  
Pinedo ML, 2012, SCHEDULING: THEORY, ALGORITHMS, AND SYSTEMS, FOURTH EDITION, P1, DOI 10.1007/978-1-4614-2361-4
[29]  
Rakrouki M.A., 2009, 39 INT C COMP IND EN
[30]   A Local Search Algorithm for the Flow Shop Scheduling Problem with Release Dates [J].
Ren, Tao ;
Guo, Meiting ;
Lin, Lin ;
Miao, Yunhui .
DISCRETE DYNAMICS IN NATURE AND SOCIETY, 2015, 2015
1234