Название: Genetic Programming for Production Scheduling
Автор: Fangfang Zhang, Su Nguyen, Yi Mei
Издательство: Springer
Серия: Machine Learning: Foundations, Methodologies, and Applications
Год: 2021
Страниц: 357
Язык: английский
Формат: pdf (true)
Размер: 10.1 MB

Scheduling, i.e., the assignment of resources to tasks and their sequencing, is an important challenge in many areas, including manufacturing, health care, construction, and even when scheduling processes within a computer. Given its wide ranging importance, it is not surprising that scheduling is one of the oldest and most researched topics in Operational Research. Yet despite the progress made over the past decades, it remains a challenging and interesting research area. Since many scheduling problems are NP-hard and thus probably never solvable to optimality in polynomial time, many people have turned to meta-heuristics like evolutionary algorithms to tackle the hardest problems.

The book Genetic Programming for Production Scheduling—An Evolutionary Learning Approach looks at scheduling from the perspective of hyper-heuristics: Rather than searching directly for the best solution to a particular problem instance, hyper-heuristics search for a heuristic that can then be applied to construct solutions to many different problem instances. Construction heuristics have been known in scheduling for a long time, most notably in the form of dispatching rules. Whenever multiple tasks compete for the same resource, the dispatching rule decides which task is to be prioritised. Examples include simple rules such as “first in first out” or “shortest processing time first”, but the scientific literature is full of sometimes quite complex dispatching rules.

Machine learning contains a set of methods to learn models from data. According to the characteristics of available data for machine learning techniques to learn from, there are four main types of learning tasks in Machine Learning: (1) supervised learning, (2) unsupervised learning, (3) semi-supervised learning, and (4) reinforcement learning. According to the ways to learn models/solutions, the paradigms in machine learning can be divided into five categories, i.e., case-based learning, inductive learning, analytic learning, connectionist learning, and genetic learning.

Evolutionary learning applies evolutionary computation to address optimisation problems in Machine Learning. Evolutionary computation is a computational intelligence technique inspired by natural evolution based on population. Evolutionary computation consists of a family of algorithms. The success of evolutionary computation relies on the improvement of individuals generation by generation. There are two main categories in EC, which are evolutionary algorithms such as genetic algorithms, genetic programming, evolution strategies, and evolutionary programming, and swarm intelligence such as particle swarm optimisation and ant colony optimisation. Evolutionary algorithms, especially genetic programming, are the focus in this book.

This book introduces readers to an evolutionary learning approach, specifically genetic programming (GP), for production scheduling. The book is divided into six parts. In Part I, it provides an introduction to production scheduling, existing solution methods, and the GP approach to production scheduling. Characteristics of production environments, problem formulations, an abstract GP framework for production scheduling, and evaluation criteria are also presented. Part II shows various ways that GP can be employed to solve static production scheduling problems and their connections with conventional operation research methods. In turn, Part III shows how to design GP algorithms for dynamic production scheduling problems and describes advanced techniques for enhancing GP’s performance, including feature selection, surrogate modeling, and specialized genetic operators. In Part IV, the book addresses how to use heuristics to deal with multiple, potentially conflicting objectives in production scheduling problems, and presents an advanced multi-objective approach with cooperative coevolution techniques or multi-tree representations. Part V demonstrates how to use multitask learning techniques in the hyper-heuristics space for production scheduling. It also shows how surrogate techniques and assisted task selection strategies can benefit multitask learning with GP for learning heuristics in the context of production scheduling. Part VI rounds out the text with an outlook on the future.

Given its scope, the book benefits scientists, engineers, researchers, practitioners, postgraduates, and undergraduates in the areas of Machine Learning, Artificial Intelligence, evolutionary computation, operations research, and industrial engineering.