Efficient scheduling using complex networks
Osamu Yamaguchi,1, ∗ Soumen Roy,2, † and Raissa M. D’Souza3, 4, ‡

arXiv:1206.2866v1 [physics.soc-ph] 3 Jun 2012

1

JFE Steel Corporation, 1-1 Minamiwatarida-cho, Kawasaki-ku, Kawasaki, 210-0855, Japan
2
Bose Institute, 93/1 Acharya Prafulla Chandra Roy Road, Kolkata 700 009, India
3
University of California, Davis, CA 95616, USA
4
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA

We consider the problem of efficiently scheduling the production of goods for a model steel manufacturing company. We propose a new approach for solving this classic problem, using techniques
from the statistical physics of complex networks in conjunction with depth-first search to generate
a successful, flexible, schedule. The schedule generated by our algorithm is more efficient and outperforms schedules selected at random from those observed in real steel manufacturing processes.
Finally, we explore whether the proposed approach could be beneficial for long term planning.

Operations research theories typically concentrate on
deriving an optimal solution under fixed assumptions.
Such assumptions of fixed, constant conditions and constraints are often necessary to adequately simplify complex real life situations in theoretical treatment of problems. Yet, this constancy of conditions severely limits the applicability of simplified algorithms to important scientific and industrial issues, such as automated,
dynamic, scheduling in various manufacturing processes
across many industries. It is also notable that even with
assumptions of invariable conditions, the computational
complexity involved in combinatorial problems such as
scheduling remains significant. To solve such combinatorial problems, approximation methods like genetic algorithms or simulated annealing are often used [1, 2].
In real-world manufacturing houses there is a continual
and often unpredictable change of circumstances, ranging from calamities, to variable market demand, to labor
strikes. A prime example of a complex constraint influencing scheduling is the storage time of finished products
which is in turn dictated by variable market demand.
The cost of prolonged storage of completed products is
prohibitive for industries who also need to be flexible to
accommodate rush production requests which can command premium pricing.
This letter proposes a new approach for scheduling and
planning of various manufacturing processes using techniques based on the statistical physics of complex networks [3–7] and classical depth-first search. We conceptualize a model steel plant by groups of products forming
networks where each distinct product is represented by a
vertex and directed edges connect products than can be
manufactured in succession as dictated by manufacturing constraints. We call this the product network. Our
proposed approach draws connections between statistical physics of complex networks and scheduling of manufacturing processes and generates significant advantages.
Firstly, it allows a rapid calculation of an efficient daily

∗
†
‡

o-yamaguchi@jfe-steel.co.jp
soumen@boseinst.ernet.in
raissa@cse.ucdavis.edu

schedule as shown herein. Secondly, the network approach could in principle lead to approximate scheduling
solutions for relatively longer times like weeks or months
where more precise traditional solutions can not be computed due to the complexity of the algorithms and increased size of the space of products that could be produced in this longer time frame. Thirdly, for strategic
decisions, like investments to increase productivity, it is
crucial to identify the improvements to be gained by reforming the constraint network, modifying it in a way
which is most efficient from the manufacturing point of
view. Fourthly, at an operational level, experience has
shown that visual information of the network structure of
products and constraints is immensely helpful to human
operators, especially less experienced operators, overseeing the manufacturing process. Lastly, a clear knowledge
of the network is of immense help when quick and decisive intervention to the schedule is required in real time
or in an emergency.
Cut bottom of preceding Furnace
Cut top of
succeeding product product

Cutter

Looper (Buffer)
Welder
Direction of the process

Cutter

FIG. 1. (Color Online) The Continuous Annealing Line which
is a core process for manufacturing diverse steel sheets.

In many steel manufacturing processes, efficiency in
productivity is achieved by welding subsequent products together. For example, a continuous annealing line
(CAL) shown in Fig. 1, allows for production of a continual stream of products from cold rolled steel sheets
while achieving a desired malleability and ductility. For
welding and a continuous temperature transition between
products, three attributes are very important in CAL
process: the width of the steel sheet, its thickness and the
annealing temperature. The first two are constraints for
welding and determine the directionality of an edge connecting together two products in the product network.
For width, a roughly decreasing transition is suitable;

2

Time

Community
=Manufacturing Lot

Monthly

=Stock

Day1
Day2
Day3

Day1
Day2
Day3
Day1
Day2
Day3

Process 1

Process 2

Process 3

FIG. 2. (Color Online) Schematic illustration of long term
multi-process planning.

while for thickness, only a permitted range of thickness
changes between two products is allowed. The third constraint imposes the condition that any two given products produced in sequence should have a common range
of annealing temperatures allowing for a smooth change
of temperature settings in the furnace.
During production, the steel products attain their final shape as a consequence of various manufacturing processes such as casting, hot rolling, cold rolling, galvanizing, etc. When groups of products are subject to similar manufacturing conditions they are classified together
into a manufacturing lot. Forming a manufacturing lot
can be quite complicated as reflected in Fig. 2. If a daily
or process specific grouping is too small to be considered
a manufacturing lot, it is possible to extend the time-axis
of Fig. 2 by a small amount to thus increase lot size and
productivity. Since multiple manufacturing processes are
involved over longer time frames, a traditional operations
research approach becomes too complex to implement.
Therefore, applying network theory methods [3–7] is an
attractive alternative approach.
The treatment of a diverse range of complex real-world
systems as networks has resulted in many advances in
the past decade [3–7]. One particularly active area of
research involves the community structure of a network,
or how a network breaks up into sub-groups of nodes
with dense connectivity within a group, but only sparse
connections between groups [8]. Such community detection algorithms, including those for large networks, concepts of overlapping versus non-overlappinng communities, and many additional features, are extensively covered in a recent comprehensive review [9]. For our purposes, we expect that the community detection algorithm
for directed networks will downsize the magnitude of the
scheduling problem for both daily scheduling and complex long-term planning. We eventually want to find the
relation between the properties of networks as quantified
by standard metrics [7] and the difficulty of scheduling,
with preliminary results included at the end of this letter.
For instance, if the product network has low clustering

FIG. 3. (Color Online) Outline of proposed approach: Nodes
of the same color belong to a community [10]. Two representative communities encircled by blue loops are shown. Inset (bottom left) shows the extracted “community network”.
Each node in this network (Group 0, 1, 2, ..., 7) represents one
of the eight communities in the parent network and is denoted
by a different color. Using Σ{edge density along the route}
as a performance metric, the solid red line on the community
network shows the optimal route. As seen, this path does
not pass through every community node, such as the one in
magenta. The bigger dark green vertex shows the constituent
nodes in the parent network explicitly, and the light green
and cyan vertices are the start and end vertices respectively
for the path through the community. A vertex which has high
betweenness [12] is expected to play a key role here.

[11] (i.e., small numbers of transitive triangles) and vertices of low degree (i.e., low connectivity), we expect that
scheduling will be difficult.
First, we attempt a solution to daily scheduling which
satisfies all manufacturing constraints. We define the difficulty of scheduling as the probability of existence of a
Hamiltonian path in the network. A Hamiltonian path
on a network is a route which passes through each vertex
in the network exactly once. To construct a Hamiltonian path (which is also an efficient path as shown below), we propose a new algorithm for CAL scheduling,
based on the community detection algorithm for a directed network discussed in Ref. [10]. Fig. 3 illustrates
the algorithm which is outlined in the following steps:
(1) Network construction: Build a basic network where
a vertex represents a product and an edge denotes two
products can be connected together by welding in CAL
process. (2) Add weights to the edges according to the
width change between products: each weight is set to one
of {99, 50, 2, 1} with higher weights assigned to more desirable transitions. It must be noted that transitions from
wide to narrow are strongly preferred in CAL finishing
lines. We categorize each product by its width in 100mm
pitch. The weight 99 is given to an edge when both vertices belong to the same width category. The weights

800 1000

1400

Width

0

20

40

60

80

0.5

1.0

1.5

Thickness

20

40

60

80

900

0

700

750

800

850

Temperature

650

50 and 2 are assigned for transitions from a wider to a
narrower product that are one and two categories distant from each other respectively. The smallest weight
is assigned to edges which have a narrow to wide width
transition. (3) Community detection: We identify community sub-graphs and build a coarser-grained community network , where each vertex represents a community
and a edge means a connection between communities.
Every edge has a weight which represents the connection
density between two communities. (4) Find an optimal
route which includes the maximum number of communities: We use Σ{edge density along the route} as a performance index and the solid red line on the community network in Fig. 3, shows an optimal route passing through
the communities. (5) Select a start vertex and an end
vertex in each community: In Fig. 3, the light green vertex and cyan vertex in the big dark green circle denote
start and end vertices, respectively. Note that a vertex
which has high betweenness centrality is expected to be
a key vertex for the solution. Betweenness centrality of
a node indicates the relative fraction of shortest paths
between all nodes that pass through this given node [12].
(6) Find a route passing inside of community from the
specified start vertex to the end vertex: We apply depth
first search to obtain a Hamiltonian path. Obviously, the
traveling salesman problem could be applied if we need
to optimize some performance index. (7) We can construct the solution from (4) and (6) and if there are any
vertices which are not included in combined solution, we
use the cheapest insertion method and obtain a complete
solution.

1800

3

0

20

40

60

80

Sequence of manufacturing

FIG. 5. (Color Online) A product schedule generated by our
algorithm, with dots indicating the attribute value for successive products. The y-axis on the left measures : width (blue)
for top figure, thickness (blue) for middle figure, and, lower
limits (blue) and upper limits (green) of annealing temperature for bottom figure (y-axis values not specified for proprietary reasons). Spikes in the red line indicate instances of
constraint violations.

15
20

30

40

50

60

Normalized Degree(%)

FIG. 4. (Color Online) Degree distributions of networks related to CAL. The red, green, blue and black denote day 4,
day 6, day 9 and aggregate over all nine days respectively.

Next, we validate our methods using nine days of daily
production data, obtained from a CAL at JFE steel [13].
Our networks vary from having 70 to 112 vertices and
from 675 to 1535 edges. Fig. 4 shows the degree distribution for three different representative days of this data
and for the aggregate data over all nine days. The difference between the distributions of the individual days
implies that the networks at hand seem to be non-self-

10
5

10

Proposed
Operator

0

0

Count of Constraint Violation

20
15
0

5

10

Frequency(%)

25

30

35

averaging [14] and it is not easy to find a simple or general
solution.

Case1 Case2 Case3 Case4 Case5 Case6 Case7 Case8 Case9

FIG. 6.
(Color Online) The comparison with operator’s
scheduling results obtained from real manufacturing process.
Constraint violations which are highly undesirable are lessened by our proposed approach.

A scheduling solution obtained by the algorithm proposed above is shown in Fig. 5, plotting the attribute
values of products manufactured in succession via this

4

1.0
0.8
0.6
0.4
0.2

0.0

Density
0.4

0.0

0.2

0.4

0.6

0.8

1.0

Clustering
0.0

0.2

0.4

0.0

0.2

0.4

0.6

0.8

1.0

0.8
0.6
0.4
0.2

0.0

Betweenness
0.6

0.8

1.0

Shortest path

0.0

0.2

0.4

0.6

0.8

1.0

0.2

1.0

0.0

0.0

0.2

0.4

0.6

0.8

1.0

schedule. The top, middle and bottom plots represent
the width, thickness and annealing temperature respectively, and hence the required transitions between subsequent products. Spikes in each figure represent constraint
violations. If there exists a constraint violation, in practice on the CAL, this means a section of steel sheet is
introduced which is not machined into a product, but
included only to implement the necessary physical constraints. Analogously, in our product network, we introduce a dummy node which is not an actual product
but is inserted for the explicit purpose of satisfying the
constraints. Thus, each constraint violation directly reduces productivity and is obviously highly undesirable.
Moreover, for any algorithm to succeed, the number of
constraint violations it introduces, must be minimal.

0.6

0.8

1.0

FIG. 7. (Color Online) Scatter plot between network metrics
and difficulty in long-term scheduling (fraction of nodes in the
longest Hamiltonian path).

Figure 6 compares the number of constraint violations
observed in practice to the number that result from our
scheduling algorithm. Clearly the solutions obtained by
our proposed algorithm are generally better than the re-

[1] Eglese R.W., 1990, European Journal of Operational Research, 46(3), 271.
[2] Davis L. (ed.), 1991, Handbook of Genetic Algorithms,
(van Nostrand Reinhold).
[3] Albert R. and Barabási A.-L., 2002, Revs. Mod. Phys.,
74, 47.
[4] Newman M.E.J., 2003, SIAM Review, 45(2), 167.
[5] Barrat A., Barthelemy M., Vespignani, A., 2008, (Cambridge University Press).
[6] Newman M.E.J., 2010, (Oxford University Press).
[7] Filkov V., Saul Z.M., Roy S., D’Souza R.M. and Devanbu
P.T., 2009, Euro Physics Letters, 86, 28003.

sults obtained manually by the operator on the workshop
floor. This implies that the community detection algorithm is quite useful for downsizing the original scheduling problem and deriving a useful solution.
Inspired by the success of our approach for daily production results, we apply our community detection algorithm to nine days of production data, where each
day’s data divides into 3 to 6 communities, with the total adding upto 45 communities. More generally we are
interested in identifying whether common network metrics like edge density, clustering co-efficient, betweenness
centrality, and average shortest path can be related with
the difficulty of long-term scheduling. We quantify the
latter, akin to our previous definition, by the fraction of
nodes included in the longest Hamiltonian Path of the
network. As shown in the Fig. 7, there is no simple linear relation between the four major network metrics and
the fractional size of Hamiltonian Path for these 45 communities. In fact, R2 for a linear regression between these
four properties of communities and Hamiltonian path is
0.14.
It is well-known that the Hamiltonian Path problem
is NP-complete and therefore it is non-trivial to find an
approach which would simplify the problem. We hope
that future research will lead to simple relations between
network metrics or properties (which are undiscovered
as yet), and the difficulty of scheduling for a long term,
large scale planning problem.
In summary, we aim to find a realistic solution to the
problem of automated scheduling which takes into account changing constraints observed in actual production processes. We propose an algorithm using community detection methods based on the statistical physics
of networks. The approach proposed herein successfully
derives a solution by downsizing the original problem.
For daily scheduling, the results obtained our algorithm
are better than those practiced on the workshop floor.
We show that it is indeed difficult to derive long-term
schedules on account of the computational complexity
involved. We hope that the approaches proposed in this
work will lead to the creation of new network metrics or
algorithms which will effectively address the challenges
of long-term scheduling.

[8] Girvan M. and Newman M.E.J, 2002, Proc. Natl. Acad.
Sci. USA, 99, 7821.
[9] Fortunato S., 2010, Physics Reports, 486, 75.
[10] Leicht E.A. and Newman M.E.J., 2008, Phys. Rev. Lett.,
100, 118703.
[11] Watts D.J. and Strogatz S.H., 1998, Nature, 393, 440
[12] Freeman L.C., 1977, Sociometry, 40, 35.
[13] JFE Steel Corporation: http://www.jfe-steel.co.jp/en/
[14] Roy S. and Bhattacharjee S.M., (2006), Physics Letters
A, 352, 13.

