A Benders decomposition approach to the weighted number of tardy jobs scheduling problem on unrelated parallel machines with production costs

被引:11
作者
M'Hallah, R. [1 ]
Al-Khamis, T. [1 ]
机构
[1] Kuwait Univ, Coll Sci, Dept Stat & Operat Res, Kuwait, Kuwait
关键词
parallel machine scheduling; weighted number of tardy jobs; machine cost; Benders decomposition; APPROXIMATION ALGORITHM; RESOURCE CONSTRAINTS; CAPACITY CONSTRAINTS; COMPLETION TIMES; MINIMIZE; SELECTION; SUBJECT; RELEASE; MODELS; SUM;
D O I
10.1080/00207543.2015.1033501
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
This paper addresses the problem of scheduling on-time jobs on unrelated parallel machines with machine production costs. The objective is to maximise the net profit which is the sum of the weights of on-time jobs and the cost of using the machines. This scheduling problem is very important and frequent in industrial settings. It is herein solved using an exact approach that applies Benders decomposition to obtain tight upper and lower bounds and uses the bounds within a branch and bound. The computational investigation shows the efficacy of the approach in solving large instances. Most importantly, the proposed approach provides a new venue for solving large-scale scheduling problems.
引用
收藏
页码:5977 / 5987
页数:11
相关论文
共 27 条
[1]   A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity [J].
Al-Khamis, Talal ;
M'Hallah, Rym .
COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (12) :1747-1759
[2]   Parallel Machine Selection and Job Scheduling to Minimize Sum of Machine Holding Cost, Total Machine Time Costs, and Total Tardiness Costs [J].
Alidaee, Bahram ;
Li, Haitao .
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2014, 11 (01) :294-+
[3]  
Angel E., 2001, LNCS, V2161, P194
[4]  
[Anonymous], 2005, Discrete Optimization
[5]   Truck scheduling in cross-docking terminals with fixed outbound departures [J].
Boysen, Nils ;
Briskorn, Dirk ;
Tschoeke, Martin .
OR SPECTRUM, 2013, 35 (02) :479-504
[6]   Parallel machine scheduling subject to auxiliary resource constraints [J].
Cakici, E. ;
Mason, S. J. .
PRODUCTION PLANNING & CONTROL, 2007, 18 (03) :217-225
[7]   An integrated job release and scheduling approach on parallel machines: An application in electric wire-harness industry [J].
Cevikcan, Emre ;
Durmusoglu, M. Bulent .
COMPUTERS & INDUSTRIAL ENGINEERING, 2014, 76 :318-332
[8]  
Chen L., 2015, APPROXIMATION ALGORI
[9]   Solving parallel machine scheduling problems by column generation [J].
Chen, ZL ;
Powell, WB .
INFORMS JOURNAL ON COMPUTING, 1999, 11 (01) :78-94
[10]   Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs [J].
Dourado, Mitre Costa ;
Rodrigues, Rosiane de Freitas ;
Szwarcfiter, Jayme Luiz .
ANNALS OF OPERATIONS RESEARCH, 2009, 169 (01) :81-91