Scheduling unrelated machines with job splitting, setup resources and sequence dependency

被引:10
作者
Avgerinos, Ioannis [1 ]
Mourtos, Ioannis [1 ]
Vatikiotis, Stavros [1 ]
Zois, Georgios [1 ]
机构
[1] Athens Univ Econ & Business, Dept Management Sci & Technol, ELTRUN Res Lab, Athens 10434, Greece
基金
欧盟地平线“2020”;
关键词
Parallel machine scheduling; sequence-dependent setup times; job splitting; benders decomposition; heuristics; textile manufacturing; COMMON DUE-DATE; PARALLEL MACHINES; GENETIC ALGORITHM; FORMULATIONS;
D O I
10.1080/00207543.2022.2102948
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
We examine the parallel machine scheduling problem where a set of jobs are to be processed by a set of unrelated parallel machines. We examine the most general among the variations for which an exact method has been proposed regarding makespan minimisation. This is because, apart from unrelated machines, we allow for (i) job splitting: each job's quantity can be split and processed by multiple machines simultaneously; (ii) sequence- and machine-dependent setup times: the setup time when job j succeeds k is different than the time when k succeeds j and varies also per machine m; and (iii) setup resource constraints: the number of setups that can be performed simultaneously on different machines is restricted. We present novel lower bound formulations and a heuristic that solves instances of up to 1000 jobs in a few minutes at an average gap of less than 20%. Then, we propose a logic-based Benders decomposition, which, coupled with our heuristic, solves instances of up to 200 jobs and 20 machines to near optimality in less than two hours. Our method is used for a broad range of instances from textile manufacturing, thus yielding valuable managerial insights on makespan's versatility under varying machines or resources.
引用
收藏
页码:5502 / 5524
页数:23
相关论文
共 60 条
[1]   Scheduling under a common due-date on parallel unrelated machines [J].
Adamopoulos, GI ;
Pappis, CP .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 105 (03) :494-501
[2]  
[Anonymous], IBM ILOG CPLEX OPT S
[3]   Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times [J].
Avalos-Rosales, Oliver ;
Angel-Bello, Francisco ;
Alvarez, Ada .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2015, 76 (9-12) :1705-1718
[4]   Partitioning procedures for solving mixed-variables programming problems [J].
Benders, J. F. .
COMPUTATIONAL MANAGEMENT SCIENCE, 2005, 2 (01) :3-19
[5]   A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines [J].
Bilyk, Andrew ;
Moench, Lars .
JOURNAL OF INTELLIGENT MANUFACTURING, 2012, 23 (05) :1621-1635
[6]  
Brucker P., 1998, SCHEDULING ALGORITHM, V2nd
[7]   Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints [J].
Chen, Jeng-Fung .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 44 (11-12) :1204-1212
[8]   Splitting versus setup trade-offs for scheduling to minimize weighted completion time [J].
Correa, Jose ;
Verdugo, Victor ;
Verschae, Jose .
OPERATIONS RESEARCH LETTERS, 2016, 44 (04) :469-473
[9]   Strong LP formulations for scheduling splittable jobs on unrelated machines [J].
Correa, Jose ;
Marchetti-Spaccamela, Alberto ;
Matuschke, Jannik ;
Stougie, Leen ;
Svensson, Ola ;
Verdugo, Victor ;
Verschae, Jose .
MATHEMATICAL PROGRAMMING, 2015, 154 (1-2) :305-328
[10]   Heuristic and exact algorithms for the identical parallel machine scheduling problem [J].
Dell'Amico, Mauro ;
Iori, Manuel ;
Martello, Silvano ;
Monaci, Michele .
INFORMS JOURNAL ON COMPUTING, 2008, 20 (03) :333-344