New publication: Machine Scheduling

New publication on Machine Scheduling

Using heuristics and exact methods in a hybridized way

There is a close link between machine scheduling and project scheduling, and the expertise in one field can often be used for the other. This is certainly true for the solution methodologies to solve these scheduling problems, and the new publication is an excellent example of the use of Operations Research techniques that we use for scheduling projects, but now apply to solve machine scheduling problems.

Most of the papers in our research field solve problems with either exact methods (that are often slow but guarantee the find the optimal solution) or heuristic methods (that are often lightning fast but can only produce a high-quality near optimal solution), but there are few examples where both are combined.

In our new paper, both methods are used. A metaheuristic solution approach is used to solve the problem in a fast and efficient way, and an exact branch-and-bound procedure is added on top of it to calculate bounds. The paper is entitled “Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem” written by members from the Faculty of Economics and Business Administration (Ghent University, Belgium) and the University of Lisbon (Portugal). It has been in the review process for a while (almost two years with 3 revisions) but finally, it has been accepted by the journal “Computers and Operations Research”.

Click on the picture to access the journal paper

The abstract of the paper is as follows: We consider the problem of scheduling a number of jobs on a number of unrelated parallel machines in order to minimize the makespan. We develop three heuristic approaches, i.e., a genetic algorithm, a tabu search algorithm and a hybridization of these heuristics with a truncated branch-and-bound procedure. This hybridization is made in order to accelerate the search process to near-optimal solutions. The branch-and-bound procedure will check whether the solutions obtained by the meta-heuristics can be scheduled within a tight upper bound. We compare the performances of these heuristics on a standard data set available in the literature. Moreover, the influence of the different heuristic parameters is examined as well. The computational experiments reveal that the hybrid heuristics are able to compete with the best known results from the literature.

The use of metaheuristics for machine scheduling is not new at the Operations Research & Scheduling group and we have blogged about this topic before:

  • Overview: Introduction to machine scheduling and a link to our machine scheduling research page.
  • Case study: Publication of a procedure to schedule the production for knitted fabrics in Belgium). This study has been awarded by Arcelor Mittal.
  • Book: The use of a genetic algorithm for machine scheduling, published as a book chapter.