The Job Shop Problem

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:

The graph below illustrates the variables and constraints in the job shop problem.

task(0, 1) task(0, 2) task(0, 3) task(1, 1) task(1, 2)) task(1, 3) task(2, 1) task(2, 2) job 0 job 1 job 2

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)]
The array 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.

Call the solver and display the results

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_jobs:
    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()

Enviar comentarios sobre…