## Job Shop Scheduling Problem

Hello,

I have a machine with 20-30 production orders that need to be sequenced in order to minimize the total makespan (which is the total time from start to finish).

Each order has a specific production time and there is a setup table that defines how much time it takes to change from one order to another.

Example:

Production Orders Table

Order - Production Time

A - 10 minutes

B - 20 minutes

C - 30 minutes

Setup Table

Origin - Destination - Change Time

A - A - 0 minutes

A - B - 10 minutes

A - C - 20 minutes

B - B - 0 minutes

B - A - 10 minutes

B - C - 20 minutes

C - C - 0 minutes

C - A - 20 minutes

C - B - 20 minutes

I am feeling lost at the moment... which procedure should I use? It seems that CLP is the most adequate one, but I don't know how to implement the setup table restriction. Should I use MILP? I know how to formulate it, but I am concerned about the total running time of that solution.

Which one do you recommend?

1 ACCEPTED SOLUTION

Accepted Solutions

## Re: Job Shop Scheduling Problem

The scheduling side of PROC CLP does not support such sequence-dependent transition times, although you can use the standard CSP side, as in this example: SAS Help Center: Car Painting Problem

Also in the CLP solver in PROC OPTMODEL: SAS Help Center: Example 6.5 Car Painting Problem

Yes, you can solve the problem with MILP, but I have a simpler and faster alternative: model this as a traveling salesman problem (TSP) in a directed graph with a dummy depot node and use the TSP algorithm in the network solver.  The orders are the nodes, and the origin-destination pairs are the arcs.  In solving the TSP, you can omit the production times because they do not depend on the tour.  Alternatively, you can absorb them into the arc weights, as shown in the following code:

``````data ProductionOrdersTable;
input Order \$ ProductionTime;
datalines;
A 10
B 20
C 30
;

data SetupTable;
input Origin \$ Destination \$ ChangeTime;
datalines;
A A 0
A B 10
A C 20
B B 0
B A 10
B C 20
C C 0
C A 20
C B 20
;

proc optmodel;
set <str> NODES;
num ProductionTime {NODES} init 0;
read data ProductionOrdersTable into NODES=[Order] ProductionTime;

set <str,str> ARCS;
num ChangeTime {ARCS} init 0;
read data SetupTable(where=(Origin ne Destination)) into ARCS=[Origin Destination] ChangeTime;

str depot = 'depot';
ARCS = ARCS union ({depot} cross NODES) union (NODES cross {depot});
NODES = NODES union {depot};

num weight {<i,j> in ARCS} = ProductionTime[i] + ChangeTime[i,j];
print weight;

set <str,str> TOUR;
num order {NODES};
solve with network / tsp direction=directed links=(weight=weight) out=(tour=TOUR order=order);
print {<i,j> in TOUR} weight;
print order;
quit;
``````
weight
A B C depot
A   20 30 10
B 30   40 20
C 50 50   30
depot 0 0 0

Problem Summary
Number of Nodes 4
Graph Direction Directed
Problem Type Traveling Salesman Problem

Solution Summary
Solver Network
Problem Type Traveling Salesman Problem
Solution Status Optimal
Objective Value 90

Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 0

Best Bound 90
Nodes 1
Iterations 12
Solution Time 0.01

  weight
A B 20
B C 40
C depot 30
depot A 0

 order
A 1
B 2
C 3
depot 4

4 REPLIES 4

## Re: Job Shop Scheduling Problem

I have just moved above message to this board (Mathematical Optimization, Discrete-Event Simulation and OR), ... coming from SAS Procedures.

Koen

## Re: Job Shop Scheduling Problem

The scheduling side of PROC CLP does not support such sequence-dependent transition times, although you can use the standard CSP side, as in this example: SAS Help Center: Car Painting Problem

Also in the CLP solver in PROC OPTMODEL: SAS Help Center: Example 6.5 Car Painting Problem

Yes, you can solve the problem with MILP, but I have a simpler and faster alternative: model this as a traveling salesman problem (TSP) in a directed graph with a dummy depot node and use the TSP algorithm in the network solver.  The orders are the nodes, and the origin-destination pairs are the arcs.  In solving the TSP, you can omit the production times because they do not depend on the tour.  Alternatively, you can absorb them into the arc weights, as shown in the following code:

``````data ProductionOrdersTable;
input Order \$ ProductionTime;
datalines;
A 10
B 20
C 30
;

data SetupTable;
input Origin \$ Destination \$ ChangeTime;
datalines;
A A 0
A B 10
A C 20
B B 0
B A 10
B C 20
C C 0
C A 20
C B 20
;

proc optmodel;
set <str> NODES;
num ProductionTime {NODES} init 0;
read data ProductionOrdersTable into NODES=[Order] ProductionTime;

set <str,str> ARCS;
num ChangeTime {ARCS} init 0;
read data SetupTable(where=(Origin ne Destination)) into ARCS=[Origin Destination] ChangeTime;

str depot = 'depot';
ARCS = ARCS union ({depot} cross NODES) union (NODES cross {depot});
NODES = NODES union {depot};

num weight {<i,j> in ARCS} = ProductionTime[i] + ChangeTime[i,j];
print weight;

set <str,str> TOUR;
num order {NODES};
solve with network / tsp direction=directed links=(weight=weight) out=(tour=TOUR order=order);
print {<i,j> in TOUR} weight;
print order;
quit;
``````
weight
A B C depot
A   20 30 10
B 30   40 20
C 50 50   30
depot 0 0 0

Problem Summary
Number of Nodes 4
Graph Direction Directed
Problem Type Traveling Salesman Problem

Solution Summary
Solver Network
Problem Type Traveling Salesman Problem
Solution Status Optimal
Objective Value 90

Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 0

Best Bound 90
Nodes 1
Iterations 12
Solution Time 0.01

  weight
A B 20
B C 40
C depot 30
depot A 0

 order
A 1
B 2
C 3
depot 4

## Re: Job Shop Scheduling Problem

The solution using the TSP algorithm seems a super efficient way of modeling this problem.

I have also been reading into the CSP procedure and the examples that you sent.

I am wondering how could I include the setup time into the car sequencing problem. For example, if turning red to green takes 20min while all the other ones take 10min and my goal is to minimize the total setup time.

## Re: Job Shop Scheduling Problem

One approach to modify the car painting example to handle the different setup times is to first create a data set:

``````data setup_time_data;
do from = 1 to 4;
do to = 1 to 4;
if from ne to then do;
if from = 1 and to = 3 then setup_time = 20;
else setup_time = 10;
output;
end;
end;
end;
run;
``````

And then replace the IsPurge and ReifyCon declarations, as shown in the following code:

``````proc optmodel;
set CARS;
/* color of each car */
num car_color {CARS};
read data car_data into CARS=[_N_] car_color=color;
num nCars = card(CARS);

/* a car is identified by its original slots */
set SLOTS = CARS;

/* maximum reshuffling of any car on the line */
num maxMove init 3;
/* which car is in slot i */
var CarInSlot {i in SLOTS} integer
>= max(1,     i - maxMove)
<= min(nCars, i + maxMove);

/* color of car in slot i */
num nColors = max {car in CARS} car_color[car];
var ColorInSlot {SLOTS} integer >= 1 <= nColors;

/* ColorInSlot[i] = car_color[CarInSlot[i]] */
con ElementCon {i in SLOTS}:
element(CarInSlot[i], car_color, ColorInSlot[i]);

/* each car can be painted only once */
con PaintOnlyOnce:
alldiff(CarInSlot);

set <num,num> PAIRS;
num setup_time {PAIRS};
read data setup_time_data into PAIRS=[from to] setup_time;

/* whether there is a purge after slot i, from color j to color k */
var IsPurge {SLOTS diff {nCars}, PAIRS} binary;

set COLORS = setof {car in CARS} car_color[car];
var IsColorInSlot {SLOTS, COLORS} binary;
con ReifyColor {i in SLOTS, c in COLORS}:
reify(IsColorInSlot[i,c], ColorInSlot[i] = c);

/* IsPurge[i,j,k] = 1 if and only if ColorInSlot[i] = j and ColorInSlot[i+1] = k */
con ReifyPurge {i in SLOTS diff {nCars}, <j,k> in PAIRS}:
reify(IsPurge[i,j,k], IsColorInSlot[i,j] + IsColorInSlot[i+1,k] = 2);

/* minimize the total time */
min TotalTime =
sum {i in SLOTS diff {nCars}, <j,k> in PAIRS} setup_time[j,k] * IsPurge[i,j,k];

/* call CLP solver */
solve;

/* write solution to data set */
create data car_ds from
{i in SLOTS} <col('S'||i)=CarInSlot[i]>
{i in SLOTS} <col('C'||i)=ColorInSlot[i]>;
quit;``````

The resulting optimal solution has objective value 50, with 5 purges, none of which are from red to green.

Discussion stats
• 4 replies
• 462 views
• 4 likes
• 3 in conversation