Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

☑ This topic is **solved**.
Need further help from the community? Please
sign in and ask a **new** question.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Posted 11-30-2021 10:50 AM
(461 views)

Hello,

Trying to learn more about SAS and this particular problem.

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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 |

Number of Links | 12 |

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 |

[1] | [2] | weight |
---|---|---|

A | B | 20 |

B | C | 40 |

C | depot | 30 |

depot | A | 0 |

[1] | order |
---|---|

A | 1 |

B | 2 |

C | 3 |

depot | 4 |

4 REPLIES 4

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

Koen

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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 |

Number of Links | 12 |

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 |

[1] | [2] | weight |
---|---|---|

A | B | 20 |

B | C | 40 |

C | depot | 30 |

depot | A | 0 |

[1] | order |
---|---|

A | 1 |

B | 2 |

C | 3 |

depot | 4 |

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Thank you so much for your reply!

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

Registration is open! SAS is returning to Vegas for an AI and analytics experience like no other! Whether you're an executive, manager, end user or SAS partner, SAS Innovate is designed for everyone on your team. Register for just $495 by 12/31/2023.

**If you are interested in speaking, there is still time to submit a session idea. More details are posted on the website. **

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.