Machine Scheduling

Research: Hybrid (meta-)heuristic optimization for single machine, parallel machine and job shop scheduling problems

The scheduling of production systems is a widely investigated branch of the operational research domain. Scheduling, in general, can be seen as the allocation of limited resources to tasks in order to optimize a certain objective function. Machine scheduling, in particular, refers to problems in a manufacturing environment where jobs have to be scheduled for processing on one or more machines to optimize one or more objectives. Within the machine scheduling field there is a large variety of problem types, based on the characteristics of the jobs, the restrictions of the process and the objectives to be optimized. By means of doctoral research at the OR&S group, several machine scheduling problems, ranging from the single machine environment to the multi-stage job shop environment (i.e. single and parallel machine scheduling problems, traditional and flexible job shop scheduling problems, etc...), with varying job characteristics, process restrictions and objective functions, were investigated. For these problems, various algorithmic optimization approaches were developed.

1. An overview of genetic algorithms for the single machine scheduling problem

We have summarized the current state-of-the-art research dealing with meta-heuristic solution procedures for the single machine scheduling problem with release times, due dates and a maximum lateness objective. The research has been written down in two papers, one published in Lecture Notes in Computer Science and presented at the EvoCOP 2011 conference held in Torino, and another one published in a book chapter.

Both papers make use of two datasets generated under a strict and controlled design. The datasets have been split up in different classes reflecting a certain degree of complexity, and can be downloaded with extra information (lower bounds, best known solutions, etc.) from this webpage.

Set1 (Dependent due dates set)
Set2 (Independent due dates set)

References:

Sels, V. and Vanhoucke, M., 2011, “A hybrid dual-population genetic algorithm for the single machine maximum lateness problem”, Lecture Notes in Computer Science, 6622, 14–25.
Sels, V. and Vanhoucke, M., 2012, “Genetic algorithms for single machine scheduling problems: a trade-off between intensifications and diversification”, In A.R. Muñoz and I.G. Rodriguez (Eds.), Handbook of Genetic Algorithms: New Research, 265-293

2. Single machine scheduling with release times and family setups

The single machine maximum lateness problem with release times was extended with family setup times. In the paper "A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups", a hybrid genetic algorithm was developed and validated on a newly developed diverse data set. This data set makes use of a new method to generate job families using a rolling horizon approach and can be downloaded from this webpage.

SMS instances with family setup times

In the paper, an extensive study of local search algorithms is performed, based on the trade-off between the intensification and diversification strategies, taking the characteristics of the problem into account. The hybrid genetic algorithm is used to perform a comprehensive analysis of the influence of the different problem parameters on the maximum lateness value and the solution quality. The results of this analysis are made available in an Excel file and can be downloaded here:

Overview of the computational results

References:

Sels, V. and Vanhoucke, M., 2012, “A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups”, Computers and Operations Research, 39, 2346-2358.

3. Single machine scheduling with precedence constraints

For the extension with precedence constraints, a relatively new solution approach, the electromagnetism algorithm (EM), is developed. This is a population-based meta-heuristic derived from the principles of the law of Coulomb. The electromagnetism algorithm is hybridized with another meta-heuristic search algorithm to exploit the advantages of both individual approaches. The hybridization of both algorithms results in an important trade-off between intensification and diversification strategies. In particular, various diversification methods to prevent early convergence are examined, such as the clever restriction of the neighborhood of the meta-heuristic and the implementation of a population control technique in the electromagnetism algorithm. The performance of the hybrid algorithm is validated on standard data instances described in the literature.

References:

Sels, V. and Vanhoucke, M., 2014, “A hybrid electromagnetism-like mechanism/tabu search procedure for the single machine scheduling problem with a maximum lateness objective”, Computers and Industrial Engineering, 67, 44-55.

4. Unrelated parallel machine scheduling problem

Another study focuses on the unrelated parallel machine scheduling problem with the objective of minimizing the makespan, for which a genetic algorithm and a tabu search algorithm were developed. These meta-heuristics were hybridized with a truncated branch-and-bound procedure in order to accelerate the search process to near-optimal solutions. In addition, the hybrid heuristics were further improved by means of an effective local search algorithm.

References:

Sels, V., Coelho, J., Dias, A.M. and Vanhoucke, M., 2014, “Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem”, Computers and Operations Research, To Appear.

5. A hybrid single and dual population search procedure for the job shop scheduling problem

A comparison between a single population genetic algorithm and a dual population scatter search procedure to solve the well-known job shop scheduling problem is presented. In contrast to the single population search performed by the genetic algorithm, the scatter search algorithm splits the population of solutions in a diverse and high-quality set to exchange information between individuals in a controlled way. Extensions from a single to a dual population by taking problem specific characteristics into account can be seen as a stimulator to add diversity in the search process, which has a positive influence on the important balance between intensification and diversification.

The paper compares the performance of the Genetic Algorithm and the Scatter Search procedure with state-of-the-art results from literature. The comparative results as well as an overview of the performance of procedures from literature can be downloaded as an excel and pdf-file from this webpage.

Excel file (with Job Shop results after year 2000)
PDF file (with Job Shop results after year 2000)

References:

Sels, V., Craeymeersch, K. and Vanhoucke, M., 2011, “A hybrid single and dual population search procedure for the job shop scheduling problem”, European Journal of Operational Research, 215, 512-523.

6. The parallel machine scheduling problem: A case study

This research studies a complex variation of the parallel machine scheduling problem (PMS), based on a case study at a Belgian manufacturer of knitted textiles. The goal of the research was to develop an algorithm which was capable of solving the company-sized problem instances including up to 750 jobs and 50 machines within a single planning horizon. Performance was measured using a combination of weighted lateness and tardiness of the specific jobs, which formed an accurate representation of the economical impact of the production schedule on the company, also taking into account the geographical dispersion of the different production locations. The problem itself included a wide range of complicating factors including release dates, due dates, unrelated machines, sequence dependent changeover times as well as problems caused by limited availability of changeover operators. The heuristic developed to solve this problem combines aspects from population based as well as local search based meta-heuristic solution techniques. Moreover, heuristic dispatching rules were developed which are capable of reducing the impact of changeover interference due to limited availability of changeover operators by 23% on average.

References:

Kerkhove, L.P. and Vanhoucke, M., 2014, "Scheduling of unrelated parallel machines with limited server availability on multiple production locations: a case study in knitted fabrics", International Journal of Production Research, 52, 2630–265

7. The flexible job shop problem: A case study

A new procedure has been developed to solve a job shop scheduling problem at a Belgian manufacturer producing industrial wheels and castors in rubber. The procedure is an extension of a hybrid shifting bottleneck procedure with a tabu search algorithm while incorporating various company specific constraints. The new procedure is used as a simulation engine to test the relevance of various scenarios in order to improve the current planning approach of the company. A detailed computational experiment highlights the main contribution of the novel procedure for the company.

References:

Sels, V., Steen, F. and Vanhoucke, M., 2011, “Applying a hybrid job shop procedure to a Belgian manufacturing company producing industrial wheels and castors in rubber”, Computers and Industrial Engineering, 61, 697-708.

8. Comparison of priority rules for the job shop scheduling problem under different objective functions

A comparison and validation of various priority rules for the job shop scheduling problem under different objective functions was made. Several priority rules from literature are used to schedule job shop problems under two flow time-related and three tardiness-related objectives. The priority rules are extended to combined scheduling rules in order to improve the performance of the currently best-known rules from literature and in order to be able to optimize various objectives at the same time. The robustness on the relative ranking of the performance quality is checked for the various priority rules when applied on larger problem instances, on the extension of multiple machines possibilities per job as well as on the introduction of sequence-dependent setup times. Moreover, the influence of dynamic arrivals of jobs has also been investigated to check the robustness on the relative ranking of the performance quality between static and dynamic job arrivals.

Appendix with abbreviations and the construction of the combined rules

References:

Sels, V., Gheysen, N. and Vanhoucke, M., 2012, “A comparison of priority rules for the job shop scheduling problem under different flow time- and tardiness-related objective functions”, International Journal of Production Research, 39, 2346-2358.