Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop Scheduling

Job shop scheduling (JSS) is a process of optimizing the use of limited resources to improve the production efficiency. JSS has a wide range of applications, such as order picking in the warehouse and vaccine delivery scheduling under a pandemic. In real-world applications, the production environment is often complex due to dynamic events, such as job arrivals over time and machine breakdown. Scheduling heuristics, e.g., dispatching rules, have been popularly used to prioritize the candidates such as machines in manufacturing to make good schedules efficiently. Genetic programming (GP), has shown its superiority in learning scheduling heuristics for JSS automatically due to its flexible representation. This survey first provides comprehensive discussions of recent designs of GP algorithms on different types of JSS. In addition, we notice that in the recent years, a range of machine learning techniques, such as feature selection and multitask learning, have been adapted to improve the effectiveness and efficiency of scheduling heuristic design with GP. However, there is no survey to discuss the strengths and weaknesses of these recent approaches. To fill this gap, this article provides a comprehensive survey on GP and machine learning techniques on automatic scheduling heuristic design for JSS. In addition, current issues and challenges are discussed to identify promising areas for automatic scheduling heuristic design in the future.