6. Local Search: the Job-Shop Problem

We enter here in a new world where we don’t try to solve a problem to optimality but seek a good solution. Remember from the sub-section Complexity theory in a few lines that some problems[1] are hard to solve. No matter how powerful our computers are[2], we quickly hit a wall if we try to solve these problems to optimality. Do we give up? Of course not! If it is not possible to compute the best solutions, we can try to find very good solutions. Enter the fascinating world of (meta-)heuristics and Local Search.

Throughout this chapter, we will use the Job-Shop Problem as an illustrative example. The Job-Shop problem is a typical difficult scheduling problem. Don’t worry if you don’t know anything about scheduling or the Job-Shop Problem, we explain this problem in details. Scheduling is one of the fields where constraint programming has been applied with great success. It is thus not surprising that the CP community has developed specific tools to solve scheduling problems. In this chapter, we introduce the ones that have been implemented in or-tools.

Overview:

We start by describing the Job-Shop Problem, the disjunctive model to represent it, two formats to encode Job-Shop Problem instances (JSSP and Taillard) and our first exact results. We next make a short stop to describe the specific primitives implemented in or-tools to solve scheduling problems. For instance, instead of using IntVar variables, we use the dedicated IntervalVars and SequenceVars.

After these preliminaries, we present Local Search and how it is implemented in the or-tools library. Beside the Job-Shop Problem, we use a dummy problem to watch the inner mechanisms of Local Search in or-tools in action:

We minimize x_0 + x_1 + \ldots + x_{n-1} where each variable has the same domain [0, n-1]. To complicate things a little bit, we add the constraint x_0 \geqslant 1.

Once we understand how to use Local Search in or-tools, we use basic LocalSearchOperators to solve the Job-Shop Problem and compare the exact and approximate results. Finally, to speed up the Local Search algorithm, we use LocalSearchFilters for the dummy problem.

Prerequisites:

Classes under scrutiny:

IntervalVar, SequenceVar, LocalSearch, LocalSearchOperator, LocalSearchFilter.

Files:

The files used in this chapter are:

  • jobshop.h: This file contains the JobShopData class that records the data for Job-Shop Problem instances. This file is used throughout all the Job-Shop examples.
  • report_jobshopdata.cc: a simple program to report the content of job-shop problem instances in JSSP or Taillard’s formats.
  • abz9: a job-shop problem instance in JSSP format.
  • 20_5_01_ta001.txt: a job-shop problem instance in Taillard’s format.
  • first_example_jssp.txt: our first example in JSSP format.
  • jobshop.cc: A basic exact implementation of the disjunctive model with IntervalVar and SequenceVar variables.
  • dummy_ls.cc: A very basic example to understand the API of Local Search in or-tools.
  • jobshop_ls.h: two basic LocalSearchOperators for the job-shop problem.
  • jobshop_ls1.cc: A basic implementation of Local Search with the SwapIntervals LocalSearchOperator.
  • jobshop_ls2.cc: A basic implementation of Local Search with the ShuffleIntervals LocalSearchOperator.
  • jobshop_ls3.cc: A basic implementation of Local Search with both the SwapIntervals and ShuffleIntervals LocalSearchOperators. We use also Local Search to find an initial solution.
  • dummy_ls_filtering.cc: The basic example extended with filtering.

The files of this chapter are NOT the same as the ones in the example directory even if they were inspired by them. In particular, Job-Shop instances with only one task per job are accepted (not that this is extremely useful).

Content:

Footnotes

[1]Actually, most interesting problems!
[2]But watch out for the next generations of computers: molecular computers (http://en.wikipedia.org/wiki/Molecular_computer) and computers based on quantum mechanics (http://en.wikipedia.org/wiki/Quantum_computer)!

Google or-tools
open source library

User's Manual

Google search

Search:

Welcome

Tutorial examples

Chapters

Part I: Basics
Part II: Customization
Part III: Routing
Part IV: Technicalities
Appendices