Discovering dispatching rules from data using imitation learning: A case study for the job-shop problem

被引:29
作者
Ingimundardottir, Helga [1 ]
Runarsson, Thomas Philip [1 ]
机构
[1] Univ Iceland, Sch Engn & Nat Sci, Reykjavik, Iceland
关键词
Scheduling; Composite dispatching rules; Performance analysis; Imitation learning; DAgger; Preference learning; HEURISTICS;
D O I
10.1007/s10951-017-0534-0
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
Dispatching rules can be automatically generated from scheduling data. This paper will demonstrate that the key to learning an effective dispatching rule is through the careful construction of the training data, , where (i) features of partially constructed schedules should necessarily reflect the induced data distribution for when the rule is applied. This is achieved by updating the learned model in an active imitation learning fashion; (ii) is labelled optimally using a MIP solver; and (iii) data need to be balanced, as the set is unbalanced with respect to the dispatching step k. Using the guidelines set by our framework the design of custom dispatching rules, for a particular scheduling application, will become more effective. In the study presented three different distributions of the job-shop will be considered. The machine learning approach considered is based on preference learning, i.e. which dispatch (post-decision state) is preferable to another.
引用
收藏
页码:413 / 428
页数:16
相关论文
共 37 条
[1]  
Andresen Michael., 2010, LiSA - A Library of Scheduling Algorithms: Handbook for Version 3.0
[2]  
[Anonymous], ABS12104876 CORR
[3]  
[Anonymous], GUR OPT VERS 6 0 0
[4]  
[Anonymous], PREDICTION LEARNING
[5]  
[Anonymous], OPERATIONS RES COMPU
[6]  
[Anonymous], INT C EV COMP THEOR
[7]   Hyper-heuristics: a survey of the state of the art [J].
Burke, Edmund K. ;
Gendreau, Michel ;
Hyde, Matthew ;
Kendall, Graham ;
Ochoa, Gabriela ;
Oezcan, Ender ;
Qu, Rong .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2013, 64 (12) :1695-1724
[8]   Case-based heuristic selection for timetabling problems [J].
Burke, EK ;
Petrovic, S ;
Qu, R .
JOURNAL OF SCHEDULING, 2006, 9 (02) :115-132
[9]  
Chang KW, 2015, PR MACH LEARN RES, V37, P2058
[10]   Advanced dispatching rules for large-scale manufacturing systems [J].
Chen, Toly ;
Rajendran, Chandrasekharan ;
Wu, Chien-Wei .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2013, 67 (1-4) :1-3