A note on the algorithm LPT-FF for a flowshop scheduling with two batch-processing machines

被引：2
作者：
Dong, Jianming [1 ]
Hu, Jueliang [1 ]
Lin, Guohui [1 ,2 ]
机构：
[1] Zhejiang Sci Tech Univ, Dept Math, Hangzhou 310018, Zhejiang, Peoples R China
[2] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
来源：
OPTIMIZATION LETTERS | 2016年 / 10卷 / 01期
基金：
加拿大自然科学与工程研究理事会; 中国国家自然科学基金;
关键词：
Flowshop scheduling; Batch-processing machine; Bin-packing; Approximation algorithm; Worst-case performance analysis; NONIDENTICAL JOB SIZES; MINIMIZING MAKESPAN; RELEASE TIMES; DATES;
D O I：
10.1007/s11590-015-0859-6
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
A flowshop scheduling problem with two batch-processing machines is investigated in this paper, with the optimization goal to minimize the makespan. When the job processing times on the two machines are positively correlated, a -approximation algorithm for this NP-hard problem was previously proposed. We show that this algorithm has a worst-case performance guarantee of .
引用
收藏
页码：109 / 118
页数：10
相关论文
共 22 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2]   Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes [J].
Cheng, Bayi ;
Yang, Shanlin ;
Hu, Xiaoxuan ;
Chen, Bo .
APPLIED MATHEMATICAL MODELLING, 2012, 36 (07) :3155-3161
[3]   Scheduling algorithm for flow shop with two batch-processing machines and arbitrary job sizes [J].
Cheng, Bayi ;
Yang, Shanlin ;
Hu, Xiaoxuan ;
Li, Kai .
INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2014, 45 (03) :571-578
[4]   Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure [J].
Dupont, L ;
Dhaenens-Flipo, C .
COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (07) :807-819
[5]  
Graham R. L., 1979, Discrete Optimisation, P287
[6]   EFFICIENT SCHEDULING ALGORITHMS FOR A SINGLE BATCH PROCESSING MACHINE [J].
IKURA, Y ;
GIMPLE, M .
OPERATIONS RESEARCH LETTERS, 1986, 5 (02) :61-65
[7]   Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan [J].
Ji, Min ;
Cheng, T. C. E. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (01) :90-98
[8]  
Johnson S. M., 1954, NAVAL RES LOGISTICS, V1, P61, DOI [10.1002/nav.3800010110, DOI 10.1002/NAV.3800010110]
[9]   A hybrid genetic heuristic for scheduling parallel batch processing. machines with arbitrary job sizes [J].
Kashan, Ali Husseinzadeh ;
Karimi, Behrooz ;
Jenabi, Masoud .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (04) :1084-1098
[10]   A note on minimizing makespan on a single batch processing machine with nonidentical job sizes [J].
Kashan, Ali Husseinzadeh ;
Karimi, Behrooz ;
Ghomi, S. M. T. Fatemi .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (27-29) :2754-2758
123