Variable Neighbourhood Search Solving Sub-problems of a Lagrangian Flexible Scheduling Problem

被引:2
作者
Haemmerle, Alexander [1 ]
Weichhart, Georg [1 ,2 ]
机构
[1] Profactor GmbH, A-4407 Steyr Gleink, Austria
[2] Johannes Kepler Univ Linz, Dept Business Informat Commun Engn, A-4040 Linz, Austria
来源
PROCEEDINGS OF THE 6TH INTERNATIONAL CONFERENCE ON OPERATIONS RESEARCH AND ENTERPRISE SYSTEMS (ICORES) | 2017年
关键词
Flexible Job Shop Scheduling; Lagrangian Relaxation; Subgradient Search; Variable Neighbourhood Search; RELAXATION APPROACH; SHOP;
D O I
10.5220/0006114102340241
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
New technologies allow the production of goods to be geographically distributed across multiple job shops. When optimising schedules of production jobs in such networks, transportation times between job shops and machines can not be neglected but must be taken into account. We have researched a mathematical formulation and implementation for flexible job shop scheduling problems, minimising total weighted tardiness, and considering transportation times between machines. Based on a time-indexed problem formulation, we apply Lagrangian relaxation, and the scheduling problem is decomposed into independent job-level sub-problems. This results in multiple single job problems to be solved. For this problem, we describe a variable neighbourhood search algorithm, efficiently solving a single flexible job (sub-) problem with many timeslots. The Lagrangian dual problem is solved with a surrogate subgradient search method aggregating the partial solutions. The performance of surrogate subgradient search with VNS is compared with a combination of dynamic programming solving sub-problems, and a standard subgradient search for the overall problem. The algorithms are benchmarked with published problem instances for flexible job shop scheduling. Based on these instances we present novel problem instances for flexible job shop scheduling with transportation times between machines, and lower and upper bounds on total weighted tardiness are calculated for these instances.
引用
收藏
页码:234 / 241
页数:8
相关论文
共 10 条
[1]   Lagrangian bounds for just-in-time job-shop scheduling [J].
Baptiste, Philippe ;
Flamini, Marta ;
Sourd, Francis .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (03) :906-915
[2]  
Bragin M A., 2014, J. Optimiz. Theory App, V164, P173
[3]  
Brandimarte P., 1993, Annals of Operations Research, V41, P157, DOI 10.1007/BF02023073
[4]   Improvement of Lagrangian Relaxation Convergence for Production Scheduling [J].
Buil, Roman ;
Angel Piera, Miquel ;
Luh, Peter B. .
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2012, 9 (01) :137-147
[5]   An alternative framework to Lagrangian relaxation approach for job shop scheduling [J].
Chen, HX ;
Luh, PB .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 149 (03) :499-512
[6]   An improvement of the Lagrangean relaxation approach for job shop scheduling: A dynamic programming method [J].
Chen, HX ;
Chu, CB ;
Proth, JM .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1998, 14 (05) :786-795
[7]   A PRACTICAL APPROACH TO JOB-SHOP SCHEDULING PROBLEMS [J].
HOITOMT, DJ ;
LUH, PB ;
PATTIPATI, KR .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1993, 9 (01) :1-13
[8]  
Kaskavelis CA, 1998, IIE TRANS, V30, P1085
[9]  
Sobeyko O., 2015, COMPUTERS OPERATIONS
[10]   An optimization-based algorithm for job shop scheduling [J].
Wang, JH ;
Luh, P ;
Zhao, X ;
Wang, JL .
SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES, 1997, 22 (2) :241-256