Evolving Time-Invariant Dispatching Rules in Job Shop Scheduling with Genetic Programming

详细信息    查看全文

• 关键词：Job shop scheduling ; Genetic programming ; Hyper ; heuristic
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10196
• 期：1
• 页码：147-163
• 丛书名：Genetic Programming
• ISBN：978-3-319-55696-3
• 卷排序：10196

文摘

Genetic Programming (GP) has achieved success in evolving dispatching rules for job shop scheduling problems, particularly in dynamic environments. However, there is still great potential to improve the performance of GP. One challenge that is yet to be addressed is the huge search space. In this paper, we propose a simple yet effective approach to improve the effectiveness and efficiency of GP. The new approach is based on a newly defined time-invariance property of dispatching rules, which is derived from the idea of translational invariance from machine learning. Then, we develop a new terminal selection scheme to guarantee the time-invariance throughout the GP process. The experimental studies show that by considering the time-invariance, GP can achieve much better rules in a much shorter time.