BookmarkSubscribeRSS Feed
☑ This topic is solved. Need further help from the community? Please sign in and ask a new question.
RLucasKI
Calcite | Level 5

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
RobPratt
SAS Super FREQ

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
 

View solution in original post

4 REPLIES 4
sbxkoenk
SAS Super FREQ

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

 

Koen

RobPratt
SAS Super FREQ

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
 
RLucasKI
Calcite | Level 5

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.

RobPratt
SAS Super FREQ

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.

SAS INNOVATE 2024

Innovate_SAS_Blue.png

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. 

Register now!

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.

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