One common scheduling problem is the job shop, in which multiple jobs are processed on several machines. Each job consists of a sequence of tasks, which must be performed in a given order, and each task must be processed on a specific machine. For example, the job could be the manufacture of a single consumer item, such as an automobile. The problem is to schedule the tasks on the machines so as to minimize the length of the schedule — the time it takes from when the jobs are first started until all the jobs are completed.
There are several constraints for the job shop problem:
- No task for a job can be started until the previous task for that job is completed.
- A machine can only work on one task at a time.
- A task, once started, must run to completion.
Example Problem
Below is a simple example of a job shop problem, in which each task is labeled by a pair of numbers (m, p) where m is the number of the machine the task must be processed on and p is the processing time of the task — the amount of time it requires. (The numbering of jobs and machines starts at 0.)
- job 0 = [(0, 3), (1, 2), (2, 2)]
- job 1 = [(0, 2), (2, 1), (1, 4)]
- job 2 = [(1, 4), (2, 3)]
In the example, job 0 has three tasks. The first, (0, 3), must be processed on machine 0 in 3 units of time. The second, (1, 2), must be processed on machine 1 in 2 units of time, and so on. Altogether, there are eight tasks.
A solution for the problem
A solution to the job shop problem is an assignment of a start time for each task, which meets the constraints given above. The diagram below shows one possible solution for the problem:
You can check that the tasks for each job are scheduled at non-overlapping time intervals, in the order given by the problem.
The length of this solution is 12, which is the first time when all three jobs are complete. However, as you will see below, this is not the optimal solution to the problem.
Variables and constraints for the problem
This section describes how to set up the variables and constraints for the problem. First, let task(i, j) denote the jth task in the sequence for job i. For example, task(0, 2) denotes the second task for job 0, which corresponds to the pair (1, 2) in the problem description.
Next, define ti, j to be the start time for task(i, j). The ti, j are the variables in the job shop problem. Finding a solution involves determining values for these variables that meet the requirement of the problem. ti.
There are two types of constraints for the job shop problem:
- Conjunctive constraints
— These arise from the condition
that for any two consecutive tasks in the same job,
the first must be completed before the second can be started. For example,
task(0, 2) and task(0, 3) are consecutive tasks for job 0.
Since the processing time for task(0, 2) is
2, the start time for task(0, 3) must be at least 2 units of time after the start time for
task 2. (Perhaps task 2 is painting a door, and it takes two hours for the paint to dry.)
As a result, you get the following constraint:
t0, 2 + 2 ≤ t0, 3
-
Disjunctive constraints — These
arise from the restriction that a machine can't work on two tasks at the same time.
For example, task(0, 2) and task(2, 1) are both processed on machine 1.
Since their processing times are 2 and 4, respectively, one of the following constraints must
hold:
t0, 2 + 2 ≤ t2, 1 (if task(0, 2) is scheduled before task(2, 1))
or
t2, 1 + 4 ≤ t0, 2 (if task(2, 1) is scheduled before task(0, 2)).
The graph below illustrates the variables and constraints in the job shop problem.
The nodes in the graph represent the tasks. The solid lines with arrows, which connect consecutive tasks for the same job, correspond to conjunctive constraints. The arrows point in the order in which the tasks must be processed.
The dashed lines, which connect tasks for the same machine, correspond to disjunctive constraints. These lines don't have arrows, because the order of these tasks is not given. In fact, assigning arrows to lines — which is the same as assigning the order of the tasks on each machine — is essential to solving the problem.
Objective for the problem
Let pi, j denotes the processing time for task(i, j). Then the end time for task(i, j) is ti, j + pi, j. So the length of a solution to the job shop problem is
maxi, j ti, j + pi, j.
where the maximum is taken over all tasks. The objective of the problem is to minimize the length over all possible solutions.
A Python solution
The following sections describe the main elements of a Python program that solves the job shop problem.
Declare the solver and define the data
The following code declares the solver and and defines the data in the problem.
# Import Python wrapper for or-tools constraint solver.
from ortools.constraint_solver import pywrapcp
def main():
# Create the solver.
solver = pywrapcp.Solver('jobshop')
machines_count = 3
jobs_count = 3
all_machines = range(0, machines_count)
all_jobs = range(0, jobs_count)
# Define data.
machines = [[0, 1, 2],
[0, 2, 1],
[1, 2]]
processing_times = [[3, 2, 2],
[2, 1, 4],
[4, 3]]
The program imports the Python wrapper, pywrapcp, to the OR-Tools constraint
programming solver. It then declares the solver by the command
solver = pywrapcp.Solver('jobshop')
Next, the program defines the data for the problem by the two arrays, machines
and processing_times. Recall the original definition of the problem:
- job 0 = [(0, 3), (1, 2), (2, 2)]
- job 1 = [(0, 2), (2, 1), (1, 4)]
- job 2 = [(1, 4), (2, 3)]
machines contains the first entries of the pairs of numbers, while
processing_times contains the second entries.
Define the variables and constraints
The following code defines the variables and constraints in the problem.
# Creates jobs.
all_tasks = {}
for i in all_jobs:
for j in range(0, len(machines[i])):
all_tasks[(i, j)] = solver.FixedDurationIntervalVar(0,
horizon,
processing_times[i][j],
False,
'Job_%i_%i' % (i, j))
# Creates sequence variables and add disjunctive constraints.
all_sequences = []
all_machines_jobs = []
for i in all_machines:
machines_jobs = []
for j in all_jobs:
for k in range(0, len(machines[j])):
if machines[j][k] == i:
machines_jobs.append(all_tasks[(j, k)])
disj = solver.DisjunctiveConstraint(machines_jobs, 'machine %i' % i)
all_sequences.append(disj.SequenceVar())
solver.Add(disj)
# Add conjunctive contraints.
for i in all_jobs:
for j in range(0, len(machines[i]) - 1):
solver.Add(all_tasks[(i, j + 1)].StartsAfterEnd(all_tasks[(i, j)]))
First, the program uses the solver's FixedDurationIntervalVar method to create
all_tasks, an array containing the variables for the time interval of each task.
This is a special type of variable in OR-Tools, called an
interval variable, which contains both the begin time and
end time for each interval.
Next, the program uses the solver's DisjunctiveConstraints method to
create the disjunctive constraints for the problem, and add them
to the solver. These prevent
tasks for the same machine from overlapping in time.
Finally, the program adds the conjunctive constraints, which prevent consecutive tasks for the same job from overlapping in time, as follows:
for i in all_jobs:
for j in range(0, len(machines[i]) - 1):
solver.Add(all_tasks[(i, j + 1)].StartsAfterEnd(all_tasks[(i, j)]))
For each job, this forces the start time of task j + 1 to occur later than the end time of task j.
Define the objective
The following code defines the objective in the problem.
# Set the objective.
obj_var = solver.Max([all_tasks[(i, len(machines[i])-1)].EndExpr()
for i in all_jobs])
The expression all_tasks[(i, len(machines[i])-1)].EndExpr() returns the
end time for the last task on machine i. By definition, the length of a solution
is the maximum of these end times over all all machines. The code above sets the
objective for the problem to be this maximum value.
Set solver options
The following code sets some standard options for the solver.
# Create search phases.
sequence_phase = solver.Phase([all_sequences[i] for i in all_machines],
solver.SEQUENCE_DEFAULT)
vars_phase = solver.Phase([obj_var],
solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
main_phase = solver.Compose([sequence_phase, vars_phase])
For example sequence_phase sets the method the solver uses when it
iteratively inserts tasks into the sequence for each machine. See
Decision builders for more details.
Create the solution collector
The following code creates a solution collector for the example, which stores the the optimal schedule, including the begin and end times for each task, and the value of the objective function.
# Create the solution collector.
collector = solver.LastSolutionCollector()
# Add the interesting variables to the SolutionCollector.
collector.Add(all_sequences)
collector.AddObjective(obj_var)
for i in all_machines:
sequence = all_sequences[i];
sequence_count = sequence.Size();
for j in range(0, sequence_count):
t = sequence.Interval(j)
collector.Add(t.StartExpr().Var())
collector.Add(t.EndExpr().Var())
The solution collector stores the values of the start time
and end time for each task as t.StartExpr() and
t.EndExpr(), respectively.
Output of the program
The following code calls the solver and prints out the optimal schedule length and task order.
# Solve the problem.
disp_col_width = 10
if solver.Solve(main_phase, [objective_monitor, collector]):
print("\nOptimal Schedule Length:", collector.ObjectiveValue(0), "\n")
sol_line = ""
sol_line_tasks = ""
print("Optimal Schedule", "\n")
for i in all_machines:
seq = all_sequences[i]
sol_line += "Machine " + str(i) + ": "
sol_line_tasks += "Machine " + str(i) + ": "
sequence = collector.ForwardSequence(0, seq)
seq_size = len(sequence)
for j in range(0, seq_size):
t = seq.Interval(sequence[j]);
# Add spaces to output to align columns.
sol_line_tasks += t.Name() + " " * (disp_col_width - len(t.Name()))
The output is shown below:
Optimal Schedule Length: 11 Optimal Schedule Machine 0: Job_0_0 Job_1_0 Machine 1: Job_2_0 Job_0_1 Job_1_2 Machine 2: Job_1_1 Job_0_2 Job_2_1
The length of the optimal schedule is 11, which is an improvement over the solution shown
previously.
The optimal schedule is displayed for each machine,
where Job_i_j represents the jth task for job i.
The following code prints the scheduled time intervals for each task:
for j in range(0, seq_size):
t = seq.Interval(sequence[j]);
sol_tmp = "[" + str(collector.Value(0, t.StartExpr().Var())) + ","
sol_tmp += str(collector.Value(0, t.EndExpr().Var())) + "] "
# Add spaces to output to align columns.
sol_line += sol_tmp + " " * (disp_col_width - len(sol_tmp))
sol_line += "\n"
sol_line_tasks += "\n"
print(sol_line_tasks)
print("Time Intervals for Tasks\n")
print(sol_line)
Here are the time intervals corresponding to the scheduled tasks above.
Task Time Intervals Machine 0: [0,3] [3,5] Machine 1: [0,4] [4,6] [6,10] Machine 2: [5,6] [6,8] [8,11]
Here's the timeline for the optimal schedule.
Entire program
Finally, here is the entire program for the job shop problem.
from __future__ import print_function
# Import Python wrapper for or-tools constraint solver.
from ortools.constraint_solver import pywrapcp
def main():
# Create the solver.
solver = pywrapcp.Solver('jobshop')
machines_count = 3
jobs_count = 3
all_machines = range(0, machines_count)
all_jobs = range(0, jobs_count)
# Define data.
machines = [[0, 1, 2],
[0, 2, 1],
[1, 2]]
processing_times = [[3, 2, 2],
[2, 1, 4],
[4, 3]]
# Computes horizon.
horizon = 0
for i in all_machines:
horizon += sum(processing_times[i])
# Creates jobs.
all_tasks = {}
for i in all_jobs:
for j in range(0, len(machines[i])):
all_tasks[(i, j)] = solver.FixedDurationIntervalVar(0,
horizon,
processing_times[i][j],
False,
'Job_%i_%i' % (i, j))
# Creates sequence variables and add disjunctive constraints.
all_sequences = []
all_machines_jobs = []
for i in all_machines:
machines_jobs = []
for j in all_jobs:
for k in range(0, len(machines[j])):
if machines[j][k] == i:
machines_jobs.append(all_tasks[(j, k)])
disj = solver.DisjunctiveConstraint(machines_jobs, 'machine %i' % i)
all_sequences.append(disj.SequenceVar())
solver.Add(disj)
# Add conjunctive contraints.
for i in all_jobs:
for j in range(0, len(machines[i]) - 1):
solver.Add(all_tasks[(i, j + 1)].StartsAfterEnd(all_tasks[(i, j)]))
# Set the objective.
obj_var = solver.Max([all_tasks[(i, len(machines[i])-1)].EndExpr()
for i in all_jobs])
objective_monitor = solver.Minimize(obj_var, 1)
# Create search phases.
sequence_phase = solver.Phase([all_sequences[i] for i in all_machines],
solver.SEQUENCE_DEFAULT)
vars_phase = solver.Phase([obj_var],
solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
main_phase = solver.Compose([sequence_phase, vars_phase])
# Create the solution collector.
collector = solver.LastSolutionCollector()
# Add the interesting variables to the SolutionCollector.
collector.Add(all_sequences)
collector.AddObjective(obj_var)
for i in all_machines:
sequence = all_sequences[i];
sequence_count = sequence.Size();
for j in range(0, sequence_count):
t = sequence.Interval(j)
collector.Add(t.StartExpr().Var())
collector.Add(t.EndExpr().Var())
# Solve the problem.
disp_col_width = 10
if solver.Solve(main_phase, [objective_monitor, collector]):
print("\nOptimal Schedule Length:", collector.ObjectiveValue(0), "\n")
sol_line = ""
sol_line_tasks = ""
print("Optimal Schedule", "\n")
for i in all_machines:
seq = all_sequences[i]
sol_line += "Machine " + str(i) + ": "
sol_line_tasks += "Machine " + str(i) + ": "
sequence = collector.ForwardSequence(0, seq)
seq_size = len(sequence)
for j in range(0, seq_size):
t = seq.Interval(sequence[j]);
# Add spaces to output to align columns.
sol_line_tasks += t.Name() + " " * (disp_col_width - len(t.Name()))
for j in range(0, seq_size):
t = seq.Interval(sequence[j]);
sol_tmp = "[" + str(collector.Value(0, t.StartExpr().Var())) + ","
sol_tmp += str(collector.Value(0, t.EndExpr().Var())) + "] "
# Add spaces to output to align columns.
sol_line += sol_tmp + " " * (disp_col_width - len(sol_tmp))
sol_line += "\n"
sol_line_tasks += "\n"
print(sol_line_tasks)
print("Time Intervals for Tasks\n")
print(sol_line)
if __name__ == '__main__':
main()