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 where each variable has the same domain . To complicate things a little bit, we add the constraint .

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:

• Basic knowledge of C++.
• Basic knowledge of Constraint Programming (see chapter Introduction to constraint programming).
• Basic knowledge of the Constraint Programming Solver (see chapter First steps with or-tools: cryptarithmetic puzzles).
• Basic knowledge about how to define an objective function (see section An implementation of the first model).
• Section Basic working of the solver: the search algorithm helps but is not mandatory.

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:

• 6.1. The Job-Shop Problem, the disjunctive model and benchmark data
  • 6.1.1. Description of the problem
  • 6.1.2. The disjunctive graph
  • 6.1.3. The disjunctive model
  • 6.1.4. The data and file formats
• 6.2. An implementation of the disjunctive model
  • 6.2.1. The IntervalVar variables
  • 6.2.2. The conjunctive constraints
  • 6.2.3. The disjunctive constraints and SequenceVars
  • 6.2.4. The objective function
  • 6.2.5. The DecisionBuilders
  • 6.2.6. The search and first results
• 6.3. Scheduling in or-tools
  • 6.3.1. Variables
  • 6.3.2. Constraints on IntervalVars
  • 6.3.3. Constraints on SequenceVars
  • 6.3.4. DecisionBuilders and Decisions for scheduling
  • 6.3.5. DependencyGraph
• 6.4. What is Local Search (LS)?
  • 6.4.1. The basic ingredients
  • 6.4.2. Is Local Search efficient?
  • 6.4.3. What about the quality of the solutions found by Local Search?
  • 6.4.4. Global optimization methods and Local Search
• 6.5. Basic working of the solver: Local Search
  • 6.5.1. The basic idea
  • 6.5.2. Overview of the Local Search Mechanism in or-tools
  • 6.5.3. The basic Local Search algorithm and the callback hooks for the SearchMonitors
• 6.6. Local Search Operators
  • 6.6.1. LocalSearchOperators
  • 6.6.2. Defining a custom LS operator
  • 6.6.3. Combining LS operators
  • 6.6.4. Interesting LS operators
• 6.7. The Job-Shop Problem: and now with Local Search!
  • 6.7.1. LocalSearchOperators: the real thing!
  • 6.7.2. The initial solution
  • 6.7.3. Exchanging two IntervalVars on a SequenceVar
  • 6.7.4. Exchanging an arbitrary number of contiguous IntervalVars on a SequenceVar
  • 6.7.5. Can we do better?
• 6.8. Filtering
  • 6.8.1. LocalSearchFilters
  • 6.8.2. Defining a custom LocalSearchFilter
  • 6.8.3. Interesting LocalSearchFilters
• 6.9. Summary

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)!