Learning Dispatching Rules for Scheduling: A Synergistic View Comprising Decision Trees, Tabu Search and Simulation
Open Access
Abstract
A promising approach for an effective shop scheduling that synergizes the benefits of the combinatorial optimization, supervised learning and discrete-event simulation is presented. Though dispatching rules are in widely used by shop scheduling practitioners, only ordinary performance rules are known; hence, dynamic generation of dispatching rules is desired to make them more effective in changing shop conditions. Meta-heuristics are able to perform quite well and carry more knowledge of the problem domain, however at the cost of prohibitive computational effort in real-time. The primary purpose of this research lies in an offline extraction of this domain knowledge using decision trees to generate simple if-then rules that subsequently act as dispatching rules for scheduling in an online manner. We used similarity index to identify parametric and structural similarity in problem instances in order to implicitly support the learning algorithm for effective rule generation and quality index for relative ranking of the dispatching decisions. Maximum lateness is used as the scheduling objective in a job shop scheduling environment.Keywords
This publication has 45 references indexed in Scilit:
- Data mining based job dispatching using hybrid simulation-optimization approach for shop scheduling problemEngineering Applications of Artificial Intelligence, 2012
- Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD lineExpert Systems with Applications, 2011
- Training a neural network to select dispatching rules in real timeComputers & Industrial Engineering, 2010
- A tabu search algorithm with a new neighborhood structure for the job shop scheduling problemComputers & Operations Research, 2007
- Rapid Modeling and Discovery of Priority Dispatching Rules: An Autonomous Learning ApproachJournal of Scheduling, 2006
- Rescheduling Manufacturing Systems: A Framework of Strategies, Policies, and MethodsJournal of Scheduling, 2003
- New and “Stronger” Job-Shop Neighbourhoods: A Focus on the Method of Nowicki and Smutnicki (1996)Journal of Heuristics, 2000
- Dynamic scheduling selection of dispatching rules for manufacturing systemInternational Journal of Production Research, 1997
- Intelligent Scheduling with Machine Learning Capabilities: The Induction of Scheduling KnowledgeIIE Transactions, 1992
- Sequencing and scheduling‐an introduction to the mathematics of the job‐shop, by Simon French, Wiley, 1982, 245 pp. Price: $49.95Networks, 1983