1312-Job Shop Scheduling.sagews

Job Shop Scheduling

Job shop scheduling is one of the classical problems of operations research. Here we demonstrate job shop scheduling for a simple example using mixed integer linear programming.

The following example comes from Chapter 4 of Christelle Gueret, Christian Prins and  Marc Sevaux, "Applications of Optimization with Xpress-MP," Dash Optimization, 2000 (this excellent summary of optimization problems is also available as a free download here.) The example consists of three printing jobs that must be processed on three color printing presses. Due to specific requirements for each job, the jobs pass through the machines in job-specific order and with differing processing times. Jobs cannot be interrupted once processing starts on a particular machine, though jobs my be queued between machines. Data for this example is summarized in the following table: ParseError: KaTeX parse error: Undefined control sequence: \Task at position 29: …{cccc}\mbox{Job\̲T̲a̲s̲k̲} & \mbox{Task …

The objective is to schedule the jobs on the machines to makespan, that is the time necessary to complete all of the jobs, subject to the given constraints.

For the purposes of this example, we manually decompose the data into a pair of python data structures.

Data Set

# Dictionary of task durations indexed by (Job, Machine) tuples

dur = {
    ('Paper 1','Blue')   : 45,
    ('Paper 1','Yellow') : 10,
    ('Paper 2','Blue')   : 20,
    ('Paper 2','Green')  : 10,
    ('Paper 2','Yellow') : 34,
    ('Paper 3','Blue')   : 12,
    ('Paper 3','Green')  : 17,
    ('Paper 3','Yellow') : 28 }

# Task sequencing indicated by pairs of (Job, Machine) tuples

order = [
    (('Paper 1','Blue'),  ('Paper 1','Yellow')),
    (('Paper 2','Green'), ('Paper 2','Blue')),
    (('Paper 2','Blue'),  ('Paper 2','Yellow')),
    (('Paper 3','Yellow'),('Paper 3','Blue')),
    (('Paper 3','Blue'),  ('Paper 3','Green')) ]

Make Span Optimization

The classic formulation for this problem was given by Alan S. Manne in "On the Job-Shop Scheduling Problem", Operations Research, Vol. 8, No. 2, pp. 219-223, 1960.

# TASKS are a list of (job,machine) tuples found from the keys for dur{}
    
TASKS = dur.keys()

# JOBS and MACHS are unduplicated lists of jobs and machines 

JOBS = sorted(list(set(zip(*TASKS)[0])))
MACHS = sorted(list(set(zip(*TASKS)[1])))

# Create MILP

JobShop = MixedIntegerLinearProgram(maximization=False)

# The objective is to minimize Makespan

MakeSpan = JobShop.new_variable(name='MakeSpan')
JobShop.set_objective(MakeSpan[0])

# MakeSpan is an upper bound on all tasks

x = JobShop.new_variable(name='TaskStartTime')
[JobShop.add_constraint(x[t] + dur[t] - MakeSpan[0], max = 0) for t in TASKS]

# Tasks must be complete in the specified order 

[JobShop.add_constraint(x[s] + dur[s] - x[t], max=0) for s,t in order]

# Disjunctive constraints to avoid machine conflicts. This uses a
# 'Big M' technique and a binary variable where y[s][t] = 0 implies
# task s must finish before task t can start and y[s][t] = 1 implies
# task t finishes before task s starts.

y = JobShop.new_variable(dim=2,vtype=JobShop.__BINARY,name='DisjY')

BigM = 1 + sum(dur[t] for t in TASKS)

CONFLICTS = [(s,t) for s in TASKS for t in TASKS if s<t and s[1]==t[1]]

[JobShop.add_constraint(BigM*y[s][t] + x[t] - x[s] - dur[s], min = 0) for s,t in CONFLICTS]
[JobShop.add_constraint(BigM*(1-y[s][t]) + x[s] - x[t] - dur[t], min = 0) for s,t in CONFLICTS]

JobShop.solve('Coin')

\newcommand{\Bold}[1]{\mathbf{#1}}97.0

Solution Report

Solution Report

# Create dictionaries for Start and Finish Times
start = dict(zip(TASKS,[JobShop.get_values(x[t]) for t in TASKS]))
finish = dict(zip(TASKS,[JobShop.get_values(x[t])+dur[t] for t in TASKS]))

# Recompute TASKS by sorting the keys of start into ascending order
TASKS = zip(*sorted(start.iteritems(), key = lambda(k,v): v))[0]

print "\n\n Makespan = %8.2f" % JobShop.get_values(MakeSpan[0])
print "\nTask Report\n"
print "     %-8s %-8s %6s %6s %6s\n" % ('Job','Machine','Start','Finish','Dur')
for t in TASKS:
    print "     %-8s %-8s %6d %6d %6d" % (t[0], t[1], start[t], finish[t], dur[t])

print "\n\nMachine Report"
print "%29s %6s %6s" % ('Dur','Start','Finish')
for m in MACHS:
    print "     %-8s" % m
    for t in TASKS:
        if m==t[1]:
            print "%-13s %-8s %6d %6d %6d" % (' ',str(t[0]), start[t], finish[t], dur[t])
    print ""

print "\n\nJob Report"
print "%29s %6s %6s" % ('Dur','Start','Finish')
for j in JOBS:
    print "     %-8s" % j
    for t in TASKS:
        if j==t[0]:
            print "%-13s %-8s %6d %6d %6d" % (' ',str(t[1]), start[t], finish[t], dur[t])
    print ""

Makespan = 97.00 Task Report Job Machine Start Finish Dur Paper 3 Yellow 0 28 28 Paper 2 Green 0 10 10 Paper 2 Blue 10 30 20 Paper 3 Blue 30 42 12 Paper 2 Yellow 30 64 34 Paper 1 Blue 42 87 45 Paper 3 Green 42 59 17 Paper 1 Yellow 87 97 10 Paper 1 Green 97 97 0 Machine Report Dur Start Finish Blue Paper 2 10 30 20 Paper 3 30 42 12 Paper 1 42 87 45 Green Paper 2 0 10 10 Paper 3 42 59 17 Paper 1 97 97 0 Yellow Paper 3 0 28 28 Paper 2 30 64 34 Paper 1 87 97 10 Job Report Dur Start Finish Paper 1 Blue 42 87 45 Yellow 87 97 10 Green 97 97 0 Paper 2 Green 0 10 10 Blue 10 30 20 Yellow 30 64 34 Paper 3 Yellow 0 28 28 Blue 30 42 12 Green 42 59 17