Parallel-machine serial-batching scheduling with release times under the effects of position-dependent learning and time-dependent deterioration

被引:26
作者
Pei, Jun [1 ,2 ]
Song, Qingru [1 ,2 ]
Liao, Baoyu [1 ,2 ]
Liu, Xinbao [1 ,2 ]
Pardalos, Panos M. [3 ]
机构
[1] Hefei Univ Technol, Sch Management, Hefei, Peoples R China
[2] Minist Educ, Key Lab Proc Optimizat & Intelligent Decis Making, Hefei, Peoples R China
[3] Univ Florida, Ctr Appl Optimizat, Dept Ind & Syst Engn, Gainesville, FL USA
基金
中国国家自然科学基金;
关键词
Parallel machines; Serial-batching; Release times; Learning effect; Deteriorating jobs; NONIDENTICAL JOB SIZES; SINGLE-MACHINE; MINIMIZING MAKESPAN; OPTIMIZATION ALGORITHM; PROCESSING MACHINES; SETUP TIME; AVAILABILITY; MAINTENANCE; CONSTRAINT; SEARCH;
D O I
10.1007/s10479-020-03555-2
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper addresses a serial-batching scheduling problem where the jobs with arbitrary release times are scheduled on parallel machines with the objective to minimize the makespan. The effects of learning and deterioration are considered simultaneously, and each job's actual processing time depends on the sum of previous jobs' processing times and the position of the current job. Each machine can process up to c jobs in the manner of serial batch, i.e., one after another with a setup time for each batch. Structural properties are identified for the special cases of the studied problem. Based on these derived structural properties, we propose a novel hybrid SC-VNS algorithm to solve the studied problem, which combines Society and Civilization (SC) algorithm with Variable Neighborhood Search (VNS). Computational experiments are conducted to evaluate the performance of the proposed hybrid algorithm and some other well-known algorithms. The results demonstrate that the proposed hybrid SC-VNS algorithm performs quite better than the compared algorithms in terms of the solution quality and the required running time.
引用
收藏
页码:407 / 444
页数:38
相关论文
共 50 条
[41]   MULTI-MACHINE SCHEDULING WITH INTERVAL CONSTRAINED POSITION-DEPENDENT PROCESSING TIMES [J].
Yu, Xianyu ;
Yang, Dar-Li ;
Zhou, Dequn ;
Zhou, Peng .
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2018, 14 (02) :803-815
[42]   Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization [J].
Soleimani, Hamed ;
Ghaderi, Hadi ;
Tsai, Pei-Wei ;
Zarbakhshnia, Navid ;
Maleki, Mohsen .
JOURNAL OF CLEANER PRODUCTION, 2020, 249
[43]   SINGLE-MACHINE BI-CRITERION SCHEDULING WITH RELEASE TIMES AND EXPONENTIALLY TIME-DEPENDENT LEARNING EFFECTS [J].
Yan, Ping ;
Wang, Ji-Bo ;
Zhao, Li-Qiang .
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2019, 15 (03) :1117-1131
[44]   Note on "A note on single machine scheduling with time-dependent deterioration and exponential learning effect" [J].
Yu, Gan-hua .
COMPUTERS & INDUSTRIAL ENGINEERING, 2021, 158
[45]   Bi-criteria single machine scheduling with a time-dependent learning effect and release times [J].
Ahmadizar, Fardin ;
Hosseini, Leila .
APPLIED MATHEMATICAL MODELLING, 2012, 36 (12) :6203-6214
[46]   Single-machine scheduling with a time-dependent deterioration [J].
Ji-Bo Wang ;
Li-Yan Wang ;
Dan Wang ;
Xiao-Yuan Wang .
The International Journal of Advanced Manufacturing Technology, 2009, 43 :805-809
[47]   Single-machine scheduling with a time-dependent deterioration [J].
Wang, Ji-Bo ;
Wang, Li-Yan ;
Wang, Dan ;
Wang, Xiao-Yuan .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 43 (7-8) :805-809
[48]   The common due-date early/tardy scheduling problem on a parallel machine under the effects of time-dependent learning and linear and nonlinear deterioration [J].
Toksari, M. Duran ;
Guner, Ertan .
EXPERT SYSTEMS WITH APPLICATIONS, 2010, 37 (01) :92-112
[49]   Scheduling on parallel identical machines with job-rejection and position-dependent processing times [J].
Gerstl, Enrique ;
Mosheiov, Gur .
INFORMATION PROCESSING LETTERS, 2012, 112 (19) :743-747
[50]   PARALLEL-MACHINE SCHEDULING WITH POTENTIAL DISRUPTION AND POSITIONAL-DEPENDENT PROCESSING TIMES [J].
Zheng, Bin ;
Fan, Min ;
Liu, Mengqi ;
Liu, Shang-Chia ;
Yin, Yunqiang .
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2017, 13 (02) :697-711