Open shop scheduling problem to minimize total weighted completion time

被引:19
作者
Bai, Danyu [1 ]
Zhang, Zhihai [2 ]
Zhang, Qiang [3 ]
Tang, Mengqian [3 ]
机构
[1] Shenyang Univ Chem Technol, Sch Econ Management, Shenyang, Peoples R China
[2] Tsinghua Univ, Dept Ind Engn, Beijing, Peoples R China
[3] Northeastern Univ, Software Coll, Shenyang, Peoples R China
基金
中国国家自然科学基金;
关键词
Scheduling; open shop; total weighted completion time; asymptotic analysis; discrete differential evolution; OPTIMIZATION;
D O I
10.1080/0305215X.2016.1164854
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
A given number of jobs in an open shop scheduling environment must each be processed for given amounts of time on each of a given set of machines in an arbitrary sequence. This study aims to achieve a schedule that minimizes total weighted completion time. Owing to the strong NP-hardness of the problem, the weighted shortest processing time block (WSPTB) heuristic is presented to obtain approximate solutions for large-scale problems. Performance analysis proves the asymptotic optimality of the WSPTB heuristic in the sense of probability limits. The largest weight block rule is provided to seek optimal schedules in polynomial time for a special case. A hybrid discrete differential evolution algorithm is designed to obtain high-quality solutions for moderate-scale problems. Simulation experiments demonstrate the effectiveness of the proposed algorithms.
引用
收藏
页码:98 / 112
页数:15
相关论文
共 15 条
[1]   SCHEDULING THE OPEN SHOP TO MINIMIZE MEAN FLOW TIME [J].
ACHUGBUE, JO ;
CHIN, FY .
SIAM JOURNAL ON COMPUTING, 1982, 11 (04) :709-720
[2]   A novel hybrid genetic algorithm for the open shop scheduling problem [J].
Ahmadizar, Fardin ;
Farahani, Mehdi Hosseinabadi .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2012, 62 (5-8) :775-787
[3]   Heuristic constructive algorithms for open shop scheduling to minimize mean flow time [J].
Braesel, Heidemarie ;
Herms, Andre ;
Moerig, Marc ;
Tautenhahn, Thomas ;
Tusch, Jan ;
Werner, Frank .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 189 (03) :856-870
[4]  
Brucker P., 1993, ZOR, Methods and Models of Operations Research, V37, P59, DOI 10.1007/BF01415528
[5]  
Chen B., 1998, Handbook of Combinatorial Optimization, P1493, DOI [DOI 10.1007/978-1-4613-0303-9_25, 10.1007/978-1-4613-0303-925, DOI 10.1007/978-1-4613-0303-925]
[6]  
Glover F., 1990, ORSA Journal on Computing, V2, P4, DOI [10.1287/ijoc.1.3.190, 10.1287/ijoc.2.1.4]
[7]  
GONZALEZ T, 1976, J ACM, V23, P665, DOI 10.1145/321978.321985
[8]   Asymptotic optimality in probability of a heuristic schedule for open shops with job overlaps [J].
Lann, A ;
Mosheiov, G ;
Rinott, Y .
OPERATIONS RESEARCH LETTERS, 1998, 22 (2-3) :63-68
[9]   The total completion time open shop scheduling problem with a given sequence of jobs on one machine [J].
Liaw, CF ;
Cheng, CY ;
Chen, MC .
COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (09) :1251-1266
[10]   Solving a multi-objective open shop scheduling problem by a novel hybrid ant colony optimization [J].
Panahi, Nadi ;
Tavakkoli-Moghaddam, Reza .
EXPERT SYSTEMS WITH APPLICATIONS, 2011, 38 (03) :2817-2822