Optimal Scheduling of Copper Concentrate Operations
Optimal Scheduling of Copper Concentrate Operations using
Continuous time Representation
Mangalam Lalpuria, Ignacio Grossman
Carnegie Mellon University
Pablo Garcia
Aurubis AG
Enterprise Wide Optimization
September 20-21, 2017
1
P
r
o
b
l
e
m
D
e
f
i
n
i
t
i
o
n
2
Given
:
•
Schedule of ships arrival
•
Initial inventory of the concentrates on both
the ships and piles on port
•
Daily arriving materials
•
Economic data
•
Capacity limits of the units
•
Interdependency Constraints
Find:
•
Optimal mixture of concentrates that must
be fed to the smelter in a given time horizon
Assumption:
•
Bins feeding the smelter are uncapacitated
•
No mixing can happen at the piles on the
port and the bins
•
Pre-blending tank and transfer ships cannot
be charged and discharged simultaneously
C
o
n
t
i
n
u
o
u
s
T
i
m
e
R
e
p
r
e
s
e
n
t
a
t
i
o
n
•
Various formulations available
•
Priority-slot based formulation is used
•
General routine for this formulation:
i.
Define the set of all transfer operations and resources
ii.
Postulate the minimum number of priority slots and increase it if obj. func.
improves
A priority slot is a position in a sequence with corresponding scheduling
priority
iii.
Exactly one operation can be assigned to each priority slot (SOS model) or
more than 1 operation can be assigned to the same slot (MOS model)
3
A
N
o
v
e
l
P
r
i
o
r
i
t
y
-
S
l
o
t
B
a
s
e
d
C
o
n
t
i
n
u
o
u
s
-
T
i
m
e
F
o
r
m
u
l
a
t
i
o
n
f
o
r
C
r
u
d
e
-
O
i
l
S
c
h
e
d
u
l
i
n
g
P
r
o
b
l
e
m
s
b
y
S
y
l
v
a
i
n
M
o
u
r
e
t
,
I
g
n
a
c
i
o
E
.
G
r
o
s
s
m
a
n
n
a
n
d
P
i
e
r
r
e
P
e
s
t
i
a
u
x
(
2
0
0
9
)
M
o
d
e
l
D
e
v
e
l
o
p
m
e
n
t
4
M
o
d
e
l
D
e
v
e
l
o
p
m
e
n
t
5
M
o
d
e
l
D
e
v
e
l
o
p
m
e
n
t
6
MINLP model
C
l
i
q
u
e
t
h
e
o
r
y
1)
What is a clique?
•
A subset W’ of the set of operations
W in which no 2 operations overlap.
•
Maximal clique – clique that is not a
subset of any other clique
2)
Why do we use cliques?
•
Helps in reducing the number of
binary variables in the model
•
Strengthens the formulation by
tightening the LP relaxation of MILP
problem
7
M
o
d
e
l
D
e
v
e
l
o
p
m
e
n
t
8
S
o
l
u
t
i
o
n
s
t
r
a
t
e
g
y
•
Proving global optimality by
solving MINLP is computationally
very expensive
•
Two-stage decomposition
strategy is used where MILP is
solved first without the non-
linearities
•
Non-linear equations are then
solved in the NLP sub-problem
after fixing the binary variable
values
•
MILP solvers: CPLEX, XPRESS
•
NLP solvers: CONOPT (local)
Baron (global)
9
C
a
s
e
S
t
u
d
y
P
r
o
b
l
e
m
10
Time Horizon: 15 days
•
2 vessels
•
3 piles on the port
•
Pre-blending tank
•
1 Daily arrival piles
•
3 bins
•
1 smelter
Vessels
Pre-Blending
Tank
Bins
Smelter
Daily Arrivals
14
6
2
8
9
7
3
12
5
11
13
10
4
16
17
1
15
•
6 copper
concentrates
•
4 key elements
V
a
r
y
i
n
g
n
u
m
b
e
r
o
f
p
r
i
o
r
i
t
y
s
l
o
t
s
11
Optimal solution
Model statistics
MILP-NLP approach
MOS model
M
o
d
e
l
S
t
a
t
i
s
t
i
c
s
12
- The same model gives infeasible solutions when solved via SOS model.
- The minimum number of slots required to give feasible solutions is 18 which
thereby shoots up the number of equations and variables by 3x!
0% gap between MILP and
NLP objective function
G
a
n
t
t
C
h
a
r
t
(
M
O
S
m
o
d
e
l
)
13
C
o
m
p
a
r
i
n
g
M
I
N
L
P
v
s
M
I
L
P
-
N
L
P
s
t
r
a
t
e
g
y
(
S
O
S
m
o
d
e
l
)
14
•
MINLP approach
Solver used: BARON
•
MILP-NLP strategy
•
Solver used:
MILP – CPLEX
NLP - CONOPT
For the case study problem
:
D
i
s
c
r
e
t
i
z
i
n
g
t
h
e
t
i
m
e
p
a
r
a
m
e
t
e
r
s
15
Model statistics
GANTT chart
C
o
n
c
l
u
s
i
o
n
s
&
F
u
t
u
r
e
W
o
r
k
•
The two-stage decomposition strategy is effective as compared to MINLP global
solver in terms of computational time
•
Objective function decreases considerably on discretizing the time parameters
•
MOS requires less priority slots as compared to SOS and thus solves quickly as
compared to it
16
•
Inclusion of other interdependency constraints and scaled parameters to
incorporate the full model size
•
Addition of sea-waiting cost in the objective function to minimize vessel
unloading time
•
Time-based continuous event formulation can be explored
This study focuses on optimizing the scheduling of copper concentrate operations, considering various factors such as ship arrivals, inventory, daily materials, economic data, and capacity limits. The goal is to find the optimal mixture of concentrates fed to the smelter within a specified time horizon using a continuous-time representation model. The formulation involves priority-slot-based scheduling, non-overlapping operations, and development of a comprehensive objective function and constraints for effective decision-making.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Optimal Scheduling of Copper Concentrate Operations using Continuous time Representation Mangalam Lalpuria, Ignacio Grossman Carnegie Mellon University Pablo Garcia Aurubis AG Enterprise Wide Optimization September 20-21, 2017 1
Problem Definition Problem Definition Given: Schedule of ships arrival Initial inventory of the concentrates on both the ships and piles on port Daily arriving materials Economic data Capacity limits of the units Interdependency Constraints Find: Optimal mixture of concentrates that must be fed to the smelter in a given time horizon Assumption: Bins feeding the smelter are uncapacitated No mixing can happen at the piles on the port and the bins Pre-blending tank and transfer ships cannot be charged and discharged simultaneously 2
Continuous Time Representation Continuous Time Representation i. ii. Various formulations available Priority-slot based formulation is used General routine for this formulation: Define the set of all transfer operations and resources Postulate the minimum number of priority slots and increase it if obj. func. improves A priority slot is a position in a sequence with corresponding scheduling priority Exactly one operation can be assigned to each priority slot (SOS model) or more than 1 operation can be assigned to the same slot (MOS model) iii. Non-overlapping operations Refers to two operations which cannot be scheduled simultaneously (such as inlet and outlet of pre-blending tank). If two non-overlapping operations v and w are assigned to priority slots i and j such that i <j, then ???+ ??? ??? A Novel Priority-Slot Based Continuous-Time Formulation for Crude-Oil Scheduling Problems by Sylvain Mouret, Ignacio E. Grossmann and Pierre Pestiaux (2009) 3
Model Development Model Development Sets i : priority slots v: operations r: resources c: copper concentrates k: key elements ??: inlet operations to resource r ??: outlet operations to resource r vs: special ordered sets Binary: Continuous: Variables ??? denotes if operation v is assigned to priority slot i ??? ,??? ??? ???(start time, duration and end time) ????? ,???? and ??? i. ii. (volume transferred during operation v if it is assigned to priority slot i) Time Volume ? ? ????? ,???? ??? ??? iii. Level (level of a resource before operation v is assigned to priority slot i) 4
Model Development Model Development Objective Function ?????? ? ? ? ? ? ?? ?? ???? where gross margin of each concentrate volume of concentrate transferred during operation v if it is assigned to the priority slot i Constraints Mass Balance i. ?????= ?0???+ ? ?,?<? ? ??????? ? ?,?<? ? ??????? ii. ????= ?0??+ ? ?,?<? ? ?????? ? ?,?<? ? ?????? iii. ??? + ? ?,?<? ? ?? ??? iv. ??? v. ????= ? ?????? vi. ????= ? ?????? ? ?,? ?,? ?,? ? ? ?,? ?,? ? ?= ?0? ? = ? ????? ? ? ?,?<? ? ?? ??? ? ? ? ?,? ? ? ?,? ? ? ?,? ?,? ? ? ?,? ?,? ? 5
Model Development Model Development MINLP model Capacity ? ? i. 0 ???? ?? ?? ????? ??? ? ?,? ?,? ? ? ?? ? ??? ii. ? ?,? ? ? ????? iii. ? ?,? ? ? ?????? ?????? ??? iv. ? ?,? ? i. ii. Time Constraints ???+ ???= ??? ?????? ??? ?????? ?????? ??? ?????? ? ?,? ? ? ?,? ? iii. ? ?,? ? Cardinality ?? ? ? ? ????? ?? i. Composition (Non-Linear) ???? ??? ??? ???? i. ? = ? ?,? ?,? ?, ? ?? ? 6
Clique theory Clique theory 1) What is a clique? A subset W of the set of operations W in which no 2 operations overlap. Maximal clique clique that is not a subset of any other clique 2) Why do we use cliques? Helps in reducing the number of binary variables in the model Strengthens the formulation by tightening the LP relaxation of MILP problem 7
Model Development Model Development Assignment Constraint ? ?,? ?????? ??? 1 ? ? Non-overlapping constraint ?,? ?,? < ?,? ?????? ???+ ??1? ???+ ?. 1 ??? ? ? ? ? ? ? ? ? ?1 ?, ?<?1<? i. ii. Precedence Constraints According to operation rules, some operations take place in a certain sequence Example: Conveyer belts have to be charged before they can start discharging or vessels unload in order of their arrival to the port Both time and assignment variables for sequences are defined to tighten the feasible space Redundancy removal constraint Due to a lot of symmetrical solutions, the CPU time starts becoming prohibitively expensive as the model size increases To reduce symmetries and non-practical solutions, tighter constraints are introduced iii. i. ii. 8
Solution strategy Solution strategy Proving global optimality by solving MINLP is computationally very expensive Two-stage decomposition strategy is used where MILP is solved first without the non- linearities Non-linear equations are then solved in the NLP sub-problem after fixing the binary variable values MILP solvers: CPLEX, XPRESS NLP solvers: CONOPT (local) Baron (global) 9
Case Study Problem Case Study Problem Vessels Pre-Blending Tank Smelter Bins 1 3 8 11 14 4 2 9 12 5 10 15 6 7 13 17 16 Daily Arrivals 2 vessels 3 piles on the port Pre-blending tank 1 Daily arrival piles 3 bins 1 smelter 6 copper concentrates 4 key elements Time Horizon: 15 days 10
Varying number of priority slots Varying number of priority slots Model statistics No of SlotsObjective function(MILP) Objective function(NLP) Time elapsed (s) Discrete vars Continuos vars Equations Non-zero elements 3 39.282 39.282 1 51 3,424 6,003 18,802 4 162.697 162.697 1.315 68 4,453 7,671 27,035 5 182.4726 infeasible 2.217 85 5,482 9,360 36,489 6 182.4726 182.4726 1.675 102 6,511 11,070 47,206 7 182.4726 182.4726 2.201 119 7,540 12,801 59,228 8 182.4726 182.4726 3.33 136 8,569 14,553 72,597 9 182.4726 182.4726 3.82 153 9,598 16,326 87,355 10 182.4726 infeasible 30 170 10,627 18,120 103,544 Optimal solution MOS model MILP-NLP approach 11
Model Statistics Model Statistics MILP Constraints Continuous variables Discrete variables Nonzero elements 11,070 6511 102 47,206 Solver Cplex (optcr = 0.00) Solution time 2s Obj 182.472 Solver Conopt Solution time 1s Obj 182.4726 NLP Constraints Continuous variables Nonzero elements Nonlinear N-Z 11,264 6,511 47,908 864 0% gap between MILP and NLP objective function - The same model gives infeasible solutions when solved via SOS model. - The minimum number of slots required to give feasible solutions is 18 which thereby shoots up the number of equations and variables by 3x! 12
Gantt Chart (MOS model) Gantt Chart (MOS model) 13
Comparing MINLP vs MILP Comparing MINLP vs MILP- -NLP strategy (SOS model) NLP strategy (SOS model) MILP CPLEX NLP - CONOPT MILP-NLP strategy Solver used: Solver used: BARON MINLP approach No of Slots Objective function 2 3 4 5 6 7 8 9 10 11 12 13 Time elapsed 0 <1 0 <1 0 126.576 132.796 143.19 156.71 160.22 166.79 170.014 170.014 170.014 7.99 13.68 24.93 35.82 32.46 107.53 270.1 31.4 88.97 191.32 No of slots Obj (MILP) Obj (NLP) Time Elapsed 5 6 7 8 9 126.576 132.796 143.19 156.71 160.22 166.79 170.014 170.014 170.014 126.576 infeasible 143.19 infeasible 160.22 166.79 170.014 170.014 170.014 <1 1.13 3.4 9.6 27.9 75.36 2.24 2.71 3.4 10 11 12 13 For the case study problem: 14
Discretizing the time parameters Discretizing the time parameters Forcing time parameters to take discrete values Introduce a new binary variable ???? such that ?????= ??? ? ?,? ? Objective value: 103.435 (much lower than 182.427!) Model statistics GANTT chart MILP Constraints Continuous variables Discrete variables Nonzero elements 11,172 7939 1530 48,736 Solver Cplex (optcr = 0.00) Solution time 4.6s Obj 103.435 Solver Conopt Solution time 2.34s Obj 103.435 15
Conclusions & Future Work Conclusions & Future Work The two-stage decomposition strategy is effective as compared to MINLP global solver in terms of computational time Objective function decreases considerably on discretizing the time parameters MOS requires less priority slots as compared to SOS and thus solves quickly as compared to it Inclusion of other interdependency constraints and scaled parameters to incorporate the full model size Addition of sea-waiting cost in the objective function to minimize vessel unloading time Time-based continuous event formulation can be explored 16
