A Lookahead Heuristic for the
Minimization of Open Stacks Problem
Marco A. M. Carvalho
[email protected]
Federal University of Ouro Preto - Brazil
Nei Y. Soma
[email protected]
Technological Institute of Aeronautics - Brazil
OR54 Annual Conference – Edinburgh, UK
04-06 September 2012
Problem Description
Motivation
Example
INTRODUCTION
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
2
Introduction
• A factory manufactures different types of products in
batches;
• Customers place orders for different products
– The contents of each order are placed in a separated
stack during manufacturing;
– When the stack receives the first product, it is opened;
– When the stack receives the last product , it is closed
• The products are delivered;
• The space is freed.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
3
Introduction
• There is a limitation on the physical space used in the
production environment
– There is not enough space for all customer’s stacks to be
opened simutaneously;
– If the number of open stacks increases beyond the
available space, stacks must be removed in order to give
space to the new stacks.
• The sequence in which the products are manufactured
can reduce the maximum number of simultaneously
open stacks
– This is the aim of the Minimization of Open Stacks Problem
(MOSP).
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
4
Motivation
• The problem is NP-Hard and has a variety of equivalent
problems:
– Cutting stock
• Cutting Patterns Sequencing.
– VLSI design
• Gate Matrix Layout Problem;
• PLA Folding.
– Graph Problems
•
•
•
•
•
•
Pathwidth;
Interval Thickness;
Node Search Game;
Narrowness;
Split bandwidth;
Edge and Vertex Separation.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
5
Example #1
• Six customers;
• Six product types.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
6
Example #1
• Manufacturing Sequence:
• Open Stacks: 0
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
7
Example #1
• Manufacturing Sequence:
• Open Stacks: 3
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
8
Example #1
• Manufacturing Sequence:
• Open Stacks: 4
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
9
Example #1
• Manufacturing Sequence:
• Open Stacks: 5
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
10
Example #1
• Manufacturing Sequence:
• Open Stacks: 4
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
11
Example #1
• Manufacturing Sequence:
• Open Stacks: 4
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
12
Example #1
• Manufacturing Sequence:
• Open Stacks: 2
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
13
Introduction
• Formally, given a boolean matrix M:
–
–
–
–
–
Rows correspond to customer’s orders;
Columns correspond to products;
mij = 1 iff order i contains product j;
mij = 0 otherwise;
Stacks are associated to rows
• First product is manufactured: stack opened;
• Last product is manufactured: stack closed;
• The objective is to find a permutation of columns such
that the maximum number of open stacks is minimized.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
14
Example #1 Revisited
p1 p2 p3 p4 p5 p6
c1
1
0
0
1
1
0
c2
1
1
0
0
0
0
c3
0
0
1
1
0
0
c4
1
1
1
0
1
0
c5
0
1
0
1
1
1
c6
0
1
0
0
0
1
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
15
Example #1 Revisited
Manufacturing Sequence
Manufacturing Sequence
p2 p4 p5 p1 p3 p6
c2
1
c3
1
1
1
c1
--
--
1
c2
1
--
--
1
Stacks
Stacks
c1
p6 p2 p1 p3 p4 p5
1
1
--
1
1
1
c4
c5
1
1
1
--
--
1
c5
c6
1
--
--
--
--
1
c6
--
1
1
1
1
1
c3
c4
Max Open Stacks: 6
1
1
1
1
--
1
1
1
--
--
1
1
1
1
Max Open Stacks: 4
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
16
Representation
Preprocessing
Breadth-First Search
Products Sequencing
Improvement Rules
A LOOKAHEAD HEURISTIC
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
17
Representation
• In MOSP graphs, nodes correspond to customer’s
orders
– Edges connect customers that ordered at least one
product in common;
– Multiple edges and loops are not considered;
– Each product produces a clique in the graph;
– There are polynomial algorithms for some special
topologies.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
18
MOSP Graph
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
19
MOSP Graph
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
20
MOSP Graph
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
21
MOSP Graph
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
22
MOSP Graph
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
23
MOSP Graph
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
24
MOSP Graph
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
25
Preprocessing #1
• If the MOSP graph is disconnected, the problem is
decomposable.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
26
Preprocessing #2
• Let c(pi) determine the set of customers that ordered
product pi
– If c(pj) ⊆ c(pi), then pi and pj can be considered as one
product.
p1 p2 p3 p4 p5 p6
p1
p2p6
p3
p4
p5
c1
1
0
0
1
1
0
c1
1
0
0
1
1
c2
1
1
0
0
0
0
c2
1
1
0
0
0
c3
0
0
1
1
0
0
c3
0
0
1
1
0
c4
1
1
1
0
1
0
c4
1
1
1
0
1
c5
0
1
0
1
1
1
c5
0
1
0
1
1
c6
0
1
0
0
0
1
c6
0
1
0
0
0
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
27
Breadth-First Search
• The MOSP resembles the Matrix Bandwidth
Minimization Problem (MBM)
– The MBM problem aims to find a permutation of rows
and columns which keeps the nonzero elements of a
matrix as close as possible to the main diagonal.
1
0
1
0
1
0
0
1
1
1
0
0
1
1
1
0
1
0
0
1
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1
1
1
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
0
0
0
1
1
1
28
Breadth-First Search
• The Cuthill-Mckee (1969) heuristic for MBM explores
a corresponding graph by Breadth-First Search (BFS):
– Choice of lower degree nodes
• Ties are broken in favor of the lower index node;
– The sequence of the search determines the
permutation of rows and columns.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
29
Breadth-First Search
• The BFS has never been applied to the MOSP
solution
– MOSP instances may not be sparse, symmetric or
square, as MBM matrices;
– The band structure is not a required condition.
• However, when applied to the MOSP, it generates
good results.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
30
Breadth-First Search
2
1
3
4
6
5
Q={3,
Q={3,
Q={3,
Q={3}
1,
Q={}
1,4,
1,4,5,
4,5,2,
5}2}6}
Not examined
Examined
All neighbors examined
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
31
Products Sequencing
• After sequencing the nodes (orders), we obtain the
products permutation:
– The orders are analyzed using LIFO policy;
– Each ordered product is inserted in the solution using
LIFO policy.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
32
Products Sequencing
• Q={3, 1, 4, 5, 2, 6}
p1 p2p6 p3
p4
p5
p2 p6
c1
1
0
0
1
1
c1
0
0
c2
1
1
0
0
0
c2
1
0
c3
0
0
1
1
0
c3
0
0
c4
1
1
1
0
1
c4
1
0
c5
0
1
0
1
1
c5
1
1
c6
0
1
0
0
0
c6
1
1
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
33
Products Sequencing
• Q={3, 1, 4, 5, 2, 6}
p1 p2p6 p3
p4
p5
p1 p2 p6
c1
1
0
0
1
1
c1
1
0
0
c2
1
1
0
0
0
c2
1
1
0
c3
0
0
1
1
0
c3
0
0
0
c4
1
1
1
0
1
c4
1
1
0
c5
0
1
0
1
1
c5
0
1
1
c6
0
1
0
0
0
c6
0
1
1
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
34
Products Sequencing
• Q={3, 1, 4, 5, 2, 6}
p1 p2p6 p3
p4
p5
p4 p5 p1 p2 p6
c1
1
0
0
1
1
c1
1
1
1
0
0
c2
1
1
0
0
0
c2
0
0
1
1
0
c3
0
0
1
1
0
c3
1
0
0
0
0
c4
1
1
1
0
1
c4
0
1
1
1
0
c5
0
1
0
1
1
c5
1
1
0
1
1
c6
0
1
0
0
0
c6
0
0
0
1
1
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
35
Products Sequencing
• Q={3, 1, 4, 5, 2, 6}
p1 p2p6 p3
p4
p5
p3 p4 p5 p1 p2 p6
c1
1
0
0
1
1
c1
0
1
1
1
0
0
c2
1
1
0
0
0
c2
0
0
0
1
1
0
c3
0
0
1
1
0
c3
1
1
0
0
0
0
c4
1
1
1
0
1
c4
1
0
1
1
1
0
c5
0
1
0
1
1
c5
0
1
1
0
1
1
c6
0
1
0
0
0
c6
0
0
0
0
1
1
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
36
Products Sequencing
Manufacturing Sequence
p3 p4 p5 p1 p2 p6
Stacks
c1
1
1
c2
1
1
1
c3
1
1
c4
1
--
1
1
1
1
1
--
1
1
1
1
c5
c6
Max Open Stacks: 4
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
37
Breadth-First Search
• Breadth-First Search features:
– Low degree nodes are not the problem’s bottleneck
• Sequenced first.
– Clique’s and high degree nodes tend to be sequenced
contiguously;
– Preprocessing #1 is inherent;
– Computational complexity;
– Ease of implementation.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
38
Improvement Rules
• Special topologies of the MOSP graph cause BFS to
generate errors:
– Cliques loosely connected;
– A dominant clique with a few nodes in its
neighborhood.
• Improvement rules:
1. Close inactive open stacks, by anticipating its
product's manufacturing;
2. Delay the opening of new stacks, by postponing its
product’s manufacturing.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
39
Improvement Rule #1
Manufacturing Sequence
p5 p2p6 p1
1
1
--
1
c1
1
1
c2
--
--
--
1
1
1
1
1
1
1
c5
1
c6
c2
c3
1
c4
c5
c6
1
p3
Max Open Stacks: 6
Stacks
Stacks
c1
p4
Manufacturing Sequence
c3
p4
p5
p1 p2p6 p3
1
1
1
1
c4
1
1
1
--
--
--
1
1
1
1
1
1
--
1
1
Max Open Stacks: 5
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
40
Improvement Rule #2
Manufacturing Sequence
p5
p3
p1 p2p6 p4
1
--
1
--
1
1
1
--
--
c2
c3
c4
1
1
1
1
c5
1
--
--
1
c6
1
Max Open Stacks: 6
c1
1
1
1
Stacks
Stacks
c1
Manufacturing Sequence
p5
p1 p2p6 p3
p4
1
1
--
--
1
1
1
1
1
c2
c3
c4
1
1
1
1
c5
1
--
1
--
c6
1
1
Max Open Stacks: 5
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
41
Data sets
Computational Environment
COMPUTATIONAL EXPERIMENTS
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
42
Datasets
• First Constraint Modeling Challenge (2005)
– 5,806 smaller instances;
– Decomposable instances;
– Polynomial topologies of MOSP graphs.
• Harder Instances (2009)
– 200 larger instances;
– No decomposable instances;
– No polynomial topologies of MOSP graphs.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
43
Computational Experiments
•
•
•
•
•
Intel i5 Quad Core 3.2 GHz processor;
16 GB RAM;
Ubuntu 12.4.1;
No optimization options;
Chu and Stuckey (2009) original code, compiled and
run as recommended
– MOSP state-of-the-art exact method.
• Implementation of Becceneri, Yanasse and Soma
(2004) as originally described
– MOSP state-of-the-art heuristic.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
44
Dataset #1
• Solutions
Method
Best solutions
Optimal solutions
Max error from optimal
Gap from Optimal
Lookahead
Becceneri et al.
832 (14%)
41 (0.71%)
5,644 (97.21%)
4,889 (84.21%)
2 stacks
8 stacks
0.18%
1.32%
• Running times (ms)
Method
Min
Mean
Max
Chu and Stuckey
0.00
1.65
6,865.00
Lookahead
0.00
29.72
1,424.00
Becceneri et al.
0.00
0.02
24.00
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
45
Dataset #1
Average Gap from Optimal
25%
gap
20%
Lookahead
Becceneri et al
15%
10%
5%
0%
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61
collections of instances
# of stacks
Average Error
4.50
4.00
3.50
3.00
2.50
2.00
1.50
1.00
0.50
0.00
Becceneri et al
Lookahead
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61
collections of instances
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
46
Dataset #2
• Solutions
Method
Lookahead
Becceneri et al.
Best solutions
144 (72%)
4 (2%)
Optimal solutions
110 (55%)
44 (22%)
4 stacks
15 stacks
1.41%
7.27%
Max error from optimal
Gap from Optimal
• Running times (ms)
Method
Min
Mean
Max
Chu and Stuckey
0.00
12,851.00
945,151.00
Lookahead
0.00
1,587.00
15,220.00
Becceneri et al.
0.00
5.34
20.00
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
47
Dataset #2
Gap from Optimal
140%
120%
Becceneri et al
Lookahead
80%
60%
40%
20%
1
6
11
16
21
26
31
36
41
46
51
56
61
66
71
76
81
86
91
96
101
106
111
116
121
126
131
136
141
146
151
156
161
166
171
176
181
186
191
196
0%
Instances
Error
16
14
12
10
8
6
4
2
0
Becceneri et al
Lookahead
1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145
151
157
163
169
175
181
187
193
199
# of stacks
gap
100%
Instances
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
48
SUMMARY
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
49
Summary
• A novel approach to MOSP;
• O(p3) heuristic, where p denotes the number of products
– Outperforms the state-of-the art heuristic in solution
quality
• Smaller gaps from optimal;
• Robust - smaller errors;
• Higher index of optimal solutions.
– Fast.
• Can be used to generate good upper bounds;
• Can be used directly to solve MOSP and equivalent
problems.
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
50
Acknowledgements
• Prof. Geoffrey Chu (University of Melbourne);
• This work was funded by the State of São Paulo
Research Foundation - FAPESP, process 2009/518319 (first author).
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
51
Questions?
THANK YOU
OR54 Annual Conference, 04-06 September 2012 – Edinburgh, UK
52