377e PDF

ROMA
TRE
UNIVERSITÀ DEGLI STUDI
Roma Tre University

Ph.D. in Computer Science and Automation
Production scheduling in
pharmaceutical industry
Luca Venditti
Advisor:
Prof. Dario Pacciarelli
Production scheduling in pharmaceutical industry
A thesis presented by
Luca Venditti
in partial fulfillment of the requirements for the degree of
Doctor of Philosophy
in Computer Science and Engineering
Roma Tre University
Dept. of Computer Science and Automation
30 March 2010
Advisor:
Prof. Dario Pacciarelli
Reviewers:
Prof. Alessandro Agnetis
Prof. Rubén Ruiz Garcı̀a
Acknowledgments
I would like to express first of all my gratitude to Prof. Pacciarelli for his
precious support and his constant helpfulness.
A particular thanks and affective regards go to my PhD colleagues and all
people that has taken part of AutOrI laboratory’s life during this years, from
hard research activity to more recreational and relaxing moments.
v
Preface
Production scheduling is the phase of production management that produces

a detailed description of operations to be executed in a given period of time,
typically short. Production planning, instead, is characterized, compared to
production scheduling, by an higher level of abstraction and a longer time pe-
riod of interest. In most manufacturing systems the two main objectives to be
achieved in production planning and scheduling are the maximization of the to-
tal value produced by the plant and the on-time delivery of the final products.
These two objectives are often in conflict with each other. Compared to other
manufacturing processes, the pharmaceutical industry gives higher importance
to on-time delivery over throughput maximization, due to the economical and
legal implications of late deliveries and stock-outs at the final customers.
Given the complexity of the production process and the issue of on-time de-
livery, it’s difficult to have plans well balanced with the production capacity.
In this contest, it is evident that scheduling is a critical operation and so, that
an automated scheduling system is important, both to obtain good schedul-
ing solutions and to have a better control of the production process. A first
aim of this thesis is to give a demonstration of the improvements that may
derive from an automated scheduling, by taking into account a real case study
of production scheduling in a pharmaceutical industry, in the specific, in its
Packaging department. At the same time, in this thesis, the issue concerning
the difficulty of solving practical scheduling problems is arisen.
Besides operations management in a single stage, another interesting issue

in production management, and in general for supply chain management, is
the coordination between stages. In the last decades there is an increasing
research activity on coordination of multiple decisions in supply chain man-
agement as well as among different stages of a production system. In the
pharmaceutical supply chain, coordination issues are particularly important to
vi
vii
achieve the high standards of product quality and availability required by the
legal and economical implications of product stock-outs at the final customers.
Availability of final products requires not only to achieve excellence at each
stage of the scheduling process but also in the coordination between different
stages. A second aim of this thesis is to investigate on the benefits that the
introduction of a centralized decision support system can bring respect to a de-
centralized one; the case study of coordination between Packaging department
and the subsequent Distribution stage of the pharmaceutical plant is addressed.
This thesis is organized as follows:
1. In Chapter 1 the production scheduling in the pharmaceutical industry

is introduced, together with a description of common features in phar-
maceutical manufacturing systems and of the the real plant considered
2. In Chapter 2 an overview of some academic problems that constitute a
basis for the resolution of real applications problems, is given. Classi-
cal formulations of these problems, together with models and algorithms,
found in literature, are first presented; in a second analysis, some gener-
alizations of classical formulations are considered, in order to gradually
step, passing through more complex problems, into resolution of real ap-
plication problems.
3. in Chapter 3 the first case study, concerning scheduling of operations in
the Packaging department, is shown. A detailed graph model and a Tabu
Search algorithm are proposed
4. in Chapter 4 the second case study on coordination between Packaging
and Distribution departments is presented. An extension of the graph
model used in the previous case study and again a Tabu Search algorithm
are proposed.
Contents
Contents viii
List of Tables x
List of Figures xi
1 Production scheduling: the pharmaceutical industry 1

1.1 Pharmaceutical manufacturing systems . . . . . . . . . . . . . . 2
1.2 An example of pharmaceutical plant . . . . . . . . . . . . . . . 7
2 Literature on scheduling problems: from theory to practice 9

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Shop scheduling problems . . . . . . . . . . . . . . . . . . . . . 13
2.5 Generalized shop scheduling problems . . . . . . . . . . . . . . 19
2.6 Multi-resource constrained scheduling problems . . . . . . . . . 23
3 Case study 1: A Tabu Search algorithm for production schedul-

ing in packaging department 26
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Description of the problem . . . . . . . . . . . . . . . . . . . . . 27
3.3 Graph representation of a solution . . . . . . . . . . . . . . . . 28
3.4 Tabu search algorithm . . . . . . . . . . . . . . . . . . . . . . . 32
3.5 Computational Experiments . . . . . . . . . . . . . . . . . . . . 41
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
viii
CONTENTS ix
4 Coordination of production scheduling and distribution in a

pharmaceutical plant 47
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Scheduling and delivery in literature . . . . . . . . . . . . . . . 49
4.3 The distribution problem . . . . . . . . . . . . . . . . . . . . . 51
4.4 Combined problem . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5 Computational experiments . . . . . . . . . . . . . . . . . . . . 60
Conclusion 64
Bibliography 67
List of Tables
3.1 Comparison between manual and computerized schedules . . . . . 44
4.1 Test for decentralized approach . . . . . . . . . . . . . . . . . . . . 62

4.2 Test for centralized approach . . . . . . . . . . . . . . . . . . . . . 62
4.3 Centralized approach with different neighborhoods . . . . . . . . . 63
x
List of Figures
1.1 The pharmaceutical supply chain . . . . . . . . . . . . . . . . . . . 4

1.2 Typical layout of a secondary pharmaceutical manufacturing plant 5
3.1 Gantt chart for machines ℎ and ℎ′ and computation of 𝑆𝑗 . . . . . 30

3.2 Node 𝑗 and weighted sequencing arcs in 𝒢(𝐻) . . . . . . . . . . . 32
3.3 Approximate evaluation of move 𝜑𝑀 (𝑖, 𝑗). . . . . . . . . . . . . . . 40
3.4 Performance of the tabu search algorithm for varying 𝑛 and 𝑚 . . 45
4.1 Graph model for the distribution problem . . . . . . . . . . . . . . 53

4.2 Graph model for the centralized resolution approach for the com-
bined problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3 Distances between customer locations (km) . . . . . . . . . . . . . 61
xi
Chapter 1
Production scheduling: the

pharmaceutical industry
Production scheduling is the phase of production management that produces a

detailed description of operations to be executed in a given period of time, typi-
cally short. This description contains, for each operation, the specification both
of resources (machines, manpower, tools) to be used, and of time when they
have to be executed. Production scheduling is often cited in combination with
production planning, that is characterized, compared to production schedul-
ing, by an higher level of abstraction and a longer time period of interest. In
fact production planning has the aim of defining the orders to be produced
in a medium or long term; the result of the production planning constitute
constraints to be respected by the scheduling phase. In most manufacturing
systems the two main objectives to be achieved in production planning and
scheduling are the maximization of the total value produced by the plant and
the on-time delivery of the final products. These two objectives are often in
conflict with each other. In fact, the former requires the organization of pro-
duction schedules with large lots, to reduce the number of setups and idle time;
instead, for the latter objective an organization with small lots is preferable,
with consequent increase of the number of setups and idle time and reduc-
tion of the factory throughput. Compared to other manufacturing processes,
the pharmaceutical industry gives higher importance to on-time delivery over
throughput maximization, due to the economical and legal implications of late
deliveries and stock-outs at the final customers.
In the pharmaceutical industry, production planning and scheduling usually in-
1
CHAPTER 1. PRODUCTION SCHEDULING: THE PHARMACEUTICAL
INDUSTRY 2
teracts as an open loop control chain, in which the planning phase determines
input data and constraints to be satisfied by the scheduling phase. In the plan-
ning phase, decisions are taken with the aim to satisfy the demand, that is not
completely known at the moment of decisions. Then, in the scheduling phase,
decisions have to be taken facing two kinds of constraints, i.e. the production
orders released by the planning stage (in term of release and due dates) and
the availability of the production resources. Hence, when the resource amount
required by the plan is not sustainable by the available capacity, the schedule
cannot comply with the plan, causing delays in the delivery of final products.
So it is important that the production planned does not exceed the capacity of
the factory. We have already stated the production planning is driven by the
demand. This demand takes the form of wholesaler orders that are typically
the result of a negotiation in which order quantities, due dates and penalties for
late delivery are regulated by contracts. Contracts stipulations should take into
account also future production capacity and evaluate the impact of new order
on due dates of those currently in the system, in order to choose sustainable
quantities and due dates. However, it is not easy to do this for various reasons,
as the complexity of manufacturing processes (given among other factors by
constraints related to contamination problems) or the issue of on-time delivery.
In fact, these factors lead to frequent under-utilization of shop resources and
disregarding of long-term due dates. As in a vicious circle, this difficulty in
estimating reliable delivery dates to negotiate with the wholesalers, may cause
frequent urgent orders, which further increase the short-term pressure on the
operations managers. Given the complexity of the production process and the
difficulty to have plans well balanced with the production capacity, scheduling
is a critical operation in pharmaceutical industry. So, the importance of an
automated scheduling system is evident, both for obtaining good scheduling
solutions and for having a better control of the production process.
The remainder of this chapter presents, in Section 1.1, a description of
common features in pharmaceutical manufacturing systems; then, a description
of the real plant object of the case studies of this thesis, is given in Section 1.2.
1.1 Pharmaceutical manufacturing systems

Typical pharmaceutical supply chain (Figure 1.1) contains at least two stages:
primary and secondary manufacturing [10, 49]. The former is dedicated to the
production of active ingredients and other basic components through complex
chemical and biochemical processes. Production is typically a push process,
INDUSTRY 3
i.e. operations are pushed to next level whether needed or not, and it is orga-
nized in long campaigns, to reduce the impact of long cleaning and setup times
that are necessary to ensure quality and avoid cross-contamination. Primary
manufacturing is therefore not very sensitive to short-term demand fluctua-
tion, and the main issue here is a careful lot sizing to avoid shortages of active
ingredients.Secondary manufacturing is usually a pull process, driven by whole-
saler orders, in which active ingredients and other components are dispensed,
blended, processed and packed to produce the final products. Secondary phar-
maceutical manufacturing systems consist of a set of multi-purpose production
facilities that produce a variety of intermediate and finished products through
multi-stage production processes. Facilities are linked by supplier-customer re-
lations, i.e., one facility produces intermediate goods that are processed further
by other facilities, reflecting the material flow relationships given by the recipes
of the final products. Furthermore, each facility may interact with external en-
tities (e.g. suppliers) and/or internal ones (e.g. warehouses). For example, the
area of interest for this thesis, i.e. the packaging area, is the one mostly con-
nected to external entities.Primary and secondary manufacturing are typically
decoupled by relatively large stocks of components.
From the point of view of production scheduling, it is more interesting to

focus on secondary manufacturing only, because at this stage, scheduling is a
critical issues to guarantee 100% availability of final products at sustainable
costs. In particular, the impact of a late delivery can be minor, as when the
delay is absorbed by the wholesaler inventory system, or major, when it may
cause a stock-out at final customers. In the latter case, a hard deadline is
associated to the product besides the due date.
Common production processes are devoted to producing solid, liquid, aerosol

or powdered items according to a family of similar recipes [10]. For example,
one of the main process families is devoted to Solid Dosage Manufacturing
(SDM), which includes, among others, the production of tablets. Each com-
mon production process consists of a set of self-contained activities.
Hence, the production is typically organized with four main departments
(with eventually a fifth, the Distribution), as in Figure 1.2 which to a certain
extent can operate independently of each other:
∙ Dispensing, where, with respect to the receipt, the availability of all

materials required is checked (raw material handling) and materials are
weighed and stored in sealed bins (dispensing).
INDUSTRY 4
Figure 1.1: The pharmaceutical supply chain
∙ Manufacturing, where most of activities are performed, i.e.: specific

agents are prepared to be used together to wet powders in the granu-
lation (binder preparation); then, dry materials from the bins are passed
into a granulator and mixed with specific quantities of binder agents to
produce, after a drying procedure, granules (granulation), that are then
stored in bins; bin contents are then blended with, eventually, the addi-
tion of new materials (blending); then granules are compressed in tablet
presses (compression); finally, a solution is prepared and sprayed over the
tablets (coating)
∙ Counting, where packages are prepared according to the different orders
and market places (counting)
∙ Packaging, in which tablets are put into packages to form the final (or
semi-final, if they are sent in bulk packages to other sites) products (pack-
aging);
INDUSTRY 5
Figure 1.2: Typical layout of a secondary pharmaceutical manufacturing plant
∙ Distribution, that constitute the final stage, where final products are
delivered to customers.
Quality assurance and control activities are distributed throughout the
whole manufacturing process. Dispensing and Manufacturing, as Counting and
Packaging, are typically decoupled by means of the sealed bins where tablets
are typically stored. When counting activities require a significant amount of
work, counting and packaging are performed in different departments. This is
a common situation in Europe, where the many different national regulations
and languages require the handling of a huge number of different packages in
the same plant [10, 39, 49].
Some common features of all departments are:
1. single-product processing, i.e. one product at a time is processed in the

department (or in one of its rooms if there are more than one) to avoid
cross-contamination between different kinds of products;
2. cleaning operations, that are executed when switching from one prod-
uct to another with the aim, again, to avoid cross-contamination; minor
cleaning is sufficient when two consecutive products belong to the same
family, i.e. they need, or they are composed (relating to tablets), by com-
INDUSTRY 6
patible raw materials; major cleaning is necessary when the raw materials
are incompatible.
3. resource constraints, that limit the number of resources that can be em-
ployed for a specific activity at any time. For example, manpower re-
sources are categorized by their respective skills and low skilled operators
can perform only a subset of simple tasks. This fact may limit, for exam-
ple, the number of tool changes that can be performed simultaneously in
a shift, when these activities involve complex mechanical operations.
4. sequencing constraints, that specify a partial ordering among the opera-
tions for a set of tasks. These constraints are typically dictated by each
specific recipe, but sequencing constraints may be required also by the
production process, by quality control or by specific management poli-
cies. For example, in some cases a task can be started only after some
equipment preventive maintenance or calibration task is finished.
These features require incorporation of a number of relevant details into

the scheduling models. For example, when switching from a product to an-
other, it may be necessary to clean a machine and to change some tools, which
involve mechanical operations. While cleaning operations can be performed
by low skilled operators, mechanical operations require specialized operators.
Moreover, different mechanical operations can be performed in parallel, and
therefore a careful model of the setup time should take into account the num-
ber of operators involved and their respective skills, besides the possible need
for minor/major cleaning. Constraints may derive from specific plant manage-
ment policies. For example, a department may prefer to organize production
such that the starting/completion time of some particular operation is aligned
with the beginning or end of a shift. Other departments may constrain each
setup operation to be completely executed within the same shift, although
there are no specific technological reasons for such requirement.
All these factors confirm the need of a scheduling decision support system
(DSS) to increase the efficiency of the factory by optimizing the use of resources
and monitoring the production process to be able to give a quick response to
changes that can occur.
INDUSTRY 7
1.2 An example of pharmaceutical plant

In this section we describe the plant object of study in this thesis, and in par-
ticular the Packaging and Distribution areas. A more complete description of
the plant and of the automated scheduling project for the whole plant can be
found in [38]. The plant is located in Italy and it supplies different European
countries. The production flow is organized into the four main phases described
above. However, while there are only one dispensing and one counting depart-
ment in the plant, manufacturing and packaging activities are organized with
several departments. The production planning of the plant follows a 4-week
rolling horizon strategy in which departments are called to solve their specific
scheduling problems. The result of the planning is a set of production orders
and a set of due dates for the final products to be delivered in weeks 3 and
4. These become due dates for the packaging department, which are propa-
gated backward to the counting and manufacturing departments, by assuming
approximately one week of lead time for each product, and to the dispens-
ing department, by assuming approximately two weeks of lead time for each
product. At the beginning of week 1, the dispensing department schedules the
production orders for weeks 1 and 2 and implements the schedule for week
1. If some products are delivered late with respect to the due dates defined
by the plan, their scheduled delivery time are used as release times for the
subsequent department. At the beginning of week 2, the manufacturing and
counting departments schedule the production orders for weeks 2 and 3 and
implement the schedule for week 2. Similarly, at the beginning of week 3 the
packaging department schedules the production orders for weeks 3 and 4 and
implements the schedule for week 3. The whole process is repeated every week,
i.e., every week each department schedules the production for the next two
weeks, to consider possible changes that may occur. For example, at the end of
each week there may be production orders in some department that have not
been delivered on schedule, or the production of one or more urgent orders is
required by the planner, e.g., in case of stock-outs for some products. In such
cases it may be necessary to re-schedule the production in different depart-
ments, since late deliveries at a department may cause lack of materials at the
subsequent department, while urgent orders cause extra requirements at the
corresponding department. Late and urgent orders are managed as orders with
strict deadlines to be processed as soon as possible. Clearly, deadlines make
it difficult to organize long campaigns, and thus reduce the actual capacity of
the departments. This reduction may cause, in turn, late deliveries at the end
of the week and such negative effects may propagate over several weeks.
INDUSTRY 8
Packaging and Distribution

The Packaging department contains three packaging lines working in parallel.
Each line can process one lot of identical products at a time and performs
all operations from the production of blisters to the final individual specific
packages. The number of lots per week processed by the packaging department
is usually much larger than for the manufacturing department. In fact, for
example, a single lot of tablets can be divided into many different lots of final
products, differing from each other only in the package (corresponding for
example to different countries)
Lines are multi-purpose, i.e. they can process more families of products with
supplementary tools. However, not all lines can use a specific tool, so lines can
process only some families of products. Tools are shared among families of
similar products and available in a limited number of copies, in most cases
there is a single copy of each tool. In each line, sequence-dependent setup and
removal times occur before and after the processing of a lot, in order to clean
and calibrate the line and to change the tool. A setup or removal time is called
minor when requiring no tool change and major in the latter case. Lines can
be unavailable in given periods for preventive maintenance operations.
Cleaning operations, mechanical configurations and lot processing require a
given amount of work for human operators, therefore lines cannot process lots
nor execute setups or removals without human resources. The same number
of operators is required by each production line. Human resources availabil-
ity is constant within a shift, but it can vary from one shift to another, the
night shift being typically less supervised. In order to reduce the risk of cross-
contaminations, the plant policy is to assign each operator to a specific line
during the whole shift. Setups and removals cannot be interrupted while the
processing of a lot on a line can be interrupted and resumed later on the same
line if the line becomes unavailable for planned maintenance or if the number
of operators in the subsequent shift is not sufficient to process the lot.
The Distribution department is the final department of the chain. Resources

are constituted by vehicles and operators. All vehicles have the same capacity
and can contains every kind of package produced. Operators can be divided into
internal operators, responsible for the freight of vehicles, and drivers. Deliveries
are usually made during the day, except in some cases of urgent orders, in which
they are made in the night.
Chapter 2
Literature on scheduling
problems: from theory to
practice
Models and algorithms known in literature are usually developed for solving
simplified versions of real application scheduling problems. However they con-
stitute a basis for the resolution of real world problems, that need more detailed
models and more sophisticated algorithms to be faced. Some extensions of most
known problems are considered in this chapter together with their models and
some neighborhood definitions for Tabu Search, that can be taken as example
of effective algorithm to solve practical problems.
2.1 Introduction
Most optimization algorithms from the scheduling literature are mainly con-
cerned with the computation of optimal or near-optimal solutions to very sim-
plified problems [40, 45]. According to the survey of Reisman, Kumar, and
Motwani [42], out of 170 articles (related to flowshop scheduling/sequencing)
published from 1952 to 1994 only 5 were judged to be true applications. On
the other hand, in the last years an increasing number of articles focus on re-
alistic scheduling models including more practical constraints than in the past
[37, 41, 45]. In this chapter we give an overview of some academic problems
that constitute a basis for the resolution of real applications problems. Classi-
cal formulations of these problems, together with models and algorithms, found
9
CHAPTER 2. LITERATURE ON SCHEDULING PROBLEMS: FROM
THEORY TO PRACTICE 10
in literature, are first presented; in a second analysis, some generalizations of

classic formulations are considered, in order to gradually step, passing through
more complex problems, into resolution of real application problems. Concern-
ing with algorithms, only heuristics has been considered, because to consider
exact algorithms would have gone out of the aim this thesis. In particular,
tabu search algorithm and related neighborhoods are treated, because it is cer-
tainly among the most successful heuristics for a large number of theoretical
and practical scheduling problems [33] and it has been chosen for solving the
two case studies in the this thesis. Among books on scheduling theory, in our
review, we mostly refer to the classification proposed by Brucker in [5] and by
Brucker and Knust in [7].
The remainder of this chapter is structured as follows. In Section 2.2 some

basic definitions for scheduling problems are given. Then, Tabu Search algo-
rithm is described in Section 2.3. In Section 2.4 we introduce shop problems,
that represent the most common environments in manufacturing scheduling.
Some generalizations of shop problems are considered in Section 2.5. Finally,
in Section 2.6 we introduce another class of problems adapt to represent real
application scheduling, the multi-resource constrained scheduling problems.
2.2 Basic definitions

A schedule is an allocation of resources in one or more time intervals to activ-
ities to be executed: a scheduling problem consists in finding a schedule such
that some constraints are satisfied and some criteria are optimized (objective
function). Usually, term machine is used to indicate the generic resource while
the term task or operation is used to indicate an activity. A job is a set of tasks
technologically related to each other.
Denoted with 𝐽𝑗 a generic job and with 𝑂1𝑗 , . . . , 𝑂𝑛𝑗 𝑗 its set of tasks, a job
is usually characterized by the following elements:
∙ a processing time 𝑝𝑖𝑗 required to process task 𝑖 of job 𝐽𝑗

∙ a set of eligible machines ℳ𝑖𝑗 for task 𝑂𝑖𝑗
∙ a release date 𝑟𝑗 indicating the time when the first task of job 𝐽𝑗 is
available for processing
∙ a due date 𝑑𝑗 within which it is preferable to complete job 𝐽𝑗
∙ a deadline 𝐷𝑗 within which job 𝐽𝑗 must be completed
Classes of scheduling problems are specified in terms of a three-field classi-

fication 𝛼∣𝛽∣𝛾, introduced by Graham et al. [20], where:
∙ the first field 𝛼 represents the shop environment. Some examples are sin-
gle machine (indicated with 1), parallel machines (𝑃 ) and multi-purpose
machines (MPM);
∙ the second field represents the constraints of the problem. Some exam-
ples are release times (𝑟𝑖 ), due dates (𝑑𝑖 ), deadlines (𝐷𝑖 ), precedence
constraints (𝑝𝑟𝑒𝑐), preemption (𝑝𝑚𝑡𝑛), sequence dependent setup times
(𝑆𝑠𝑑 ) and resource unavailability (𝑢𝑛𝑎𝑣𝑎𝑙𝑗 );
∙ the third field represents the optimality criteria of the problem. Some
examples are: makespan (𝐶𝑚𝑎𝑥 ), i.e. the maximum value, among all
jobs, of their completion times 𝐶𝑗 ; maximum lateness (𝐿𝑚𝑎𝑥 ), i.e. the
maximum value, among all jobs, of 𝐶𝑗 − 𝑑𝑗 ; maximum tardiness (𝑇𝑚𝑎𝑥 ),
∑𝑛 positive value, among all jobs, of 𝐶𝑗 − 𝑑𝑗 ; total comple-
i.e the maximum
tion time ( 1 𝐶𝑗 ), i.e. the sum of completion times of jobs. Optimality
criteria may be more than one (multi-criteria or multi-objective prob-
lems); in this case a priority may be given to a criterion rather than to
another (for example 𝐿𝑒𝑥(𝐶𝑚𝑎𝑥 , 𝑇𝑚𝑎𝑥 ) indicates the minimization of the
two objectives in the lexicographic order)
2.3 Tabu Search

Among the most effective algorithms for solving practical scheduling problems
there is Tabu Search algorithm, that is an evolution of Local Search algorithm.
Local Search is an algorithm that, given a solution, searches for better solu-
tions among those near to the given one. This set of near solutions is obtained
by applying an operator (move) to the current solution and it is called neigh-
borhood ; when the neighborhood does not contains better solutions than the
current one, the algorithm stops. The current solution is called local optimum.
Tabu Search is a local search algorithm which makes extensive use of mem-
ory for guiding the search. It takes its origins from ideas of Glover [15, 16]
stimulated by the need for overcoming limits of Local Search, in which the
exploration of the solution space is bounded by feasibility and local optimal-
ity criteria. The key concept at the basis of Tabu Search, in fact, is that an
optimization algorithm, in order to be effective and efficient, must provide a

large exploration of solutions but at the same time this exploration must be
dynamically guided in an intelligent way that can be represented by two as-
pects: a memory of the past exploration (adaptive memory) and the ability to
change strategy during the exploration (responsive exploration).In particular,
the adaptive memory is the main feature of Tabu Search together with the
neighborhood. The information stored in this memory is used to modify the
neighborhood 𝑁 (𝑥) of the current solution 𝑥 to obtain a new neighborhood
𝑁 ∗ (𝑥) that is used for the exploration. The term adaptive memory can refers
to various forms of memory introduced over the years with the development of
more sophisticated tabu search procedures. This memory can be explicit, when
the entire solutions are stored, or implicit, when solution attributes changed in
the recent past, usually the moves performed, are stored. A first classification
in this variety can be made, for example, between short term and long term
memory. A short term memory is usually an implicit memory where only in-
formation on the recent past of the exploration is available and typically this
information is used to determine elements that have to be excluded from 𝑁 (𝑥)
to obtain 𝑁 ∗ (𝑥), that consequently is a subset of 𝑁 (𝑥). In a long term mem-
ory, instead, information on a more ancient past of the exploration is available
and typically this information is used to include additional elements in 𝑁 ∗ (𝑥)
together with elements of 𝑁 (𝑥). However, when we deal with Tabu Search
in its basic scheme, we commonly refer to a short term memory, called tabu
list, that keeps track of last solution explored during the recent past by storing
the opposites of moves performed. A simple mechanism, combining the use
of tabu list with the permission to explore non-improving solutions, gives the
possibility to escape from local optima. In fact, if the current solution is a local
optima the best non-improving solution can be selected as the new incumbent.
At the next iteration, in a memory-less algorithm, optimality criteria would
cause the algorithm to re-visit the last local optimum, thus establishing a cy-
cle in the execution of the algorithm. This can be avoided by considering for
the exploration the modified neighborhood 𝑁 ∗ (𝑥) in which the last solutions
visited are excluded. However, this mechanism does not guarantee the escape
from local optima in any case. Problems are related to the tabu list length. In
fact tabu list is a first-in first-out list, so a move is kept in it for a number of
iterations equal to the tabu list size so in some cases this number may be not
sufficiently high to avoid the algorithm to return to the last local optimum vis-
ited. To face this problem more advanced algorithms feature a dynamic tabu
list size. Another problem may arise when a solution obtainable with a tabu
move is better than the best solution known at the current iteration; in this
case the move can be deleted from the tabu list and the corresponding solution
mantained in 𝑁 ∗ (𝑥). In general, criteria used to delete a move from the tabu
list are called aspiration criteria.
Concerning to long term memory, its most common use consists in storing se-
lected elite solutions, i.e. high quality local optima; for this reason long term
memory is usually explicit. These solutions are typically involved in responsive
exploration strategies as diversification and intensification. Intensification con-
sists in exploring regions of the solution space that are considered particularly
good, while diversification aims to explore unvisited regions. These regions are
reached by moving the search to new solutions obtained from selected elite solu-
tions; specifically, in the case of intensification strategy, selected elite solutions
with similar components are assembled together to form new solutions, while
in the case of diversification strategy, elite solutions with different features are
combined.
Examples in the literature of sophisticated TS schemes for scheduling problems
are [13, 36].
2.4 Shop scheduling problems

In this section we discuss shop scheduling problems, such as open shop prob-
lems, flow shop problems, job shop problems, and mixed shop problems, which
are widely used for modeling industrial production processes. All of these prob-
lems are special cases of the general shop problem, defined in the following.
A set ℳ of 𝑚 machines 𝑀1 , . . . , 𝑀𝑚 and a set 𝒥 of 𝑛 jobs 𝐽𝑗 with 𝑗 =
1, . . . , 𝑛 are given. Job 𝐽𝑗 consists of 𝑛𝑗 operations 𝑂𝑖𝑗 with 𝑖 = 1, . . . , 𝑛𝑗
with processing times 𝑝𝑖𝑗 . Each operation 𝑂𝑖𝑗 must be processed on a machine
𝜇𝑖𝑗 ∈ ℳ. There may be precedence relations between the operations of all
jobs. Each job can only be processed by one machine at a time and each
machine can only process one job at a time. The objective is to find a feasible
schedule that minimizes some objective function of the completion times 𝐶𝑗 of
the jobs 𝑗 = 1, . . . , 𝑛. The objective functions are assumed to be regular, i.e.
non-decreasing functions of 𝐶𝑗
Job shop
The Job Shop Scheduling Problem (JSSP or Job-Shop) is one of the most
studied combinatorial optimization problems in literature. The classic job-
shop scheduling problem may be formulated as follows. A set ℳ of 𝑚 machines
𝑀1 , . . . , 𝑀𝑚 and a set 𝒥 of 𝑛 jobs 𝐽1 , . . . , 𝐽𝑛 are given. Job 𝐽𝑗 consists of 𝑛𝑗

operations 𝑂𝑖 𝑗 with 𝑖 = 1, . . . , 𝑛𝑗 which have to be processed in the order
𝑂1𝑗 → 𝑂2𝑗 , . . . , 𝑂𝑛𝑗 𝑗 . Operation 𝑂𝑖𝑗 must be processed for a processing time
𝑝𝑖𝑗 > 0 on a dedicated machine 𝜇𝑖𝑗 ∈ 𝑀1 , ..., 𝑀𝑚 . Each machine can process
only one job at a time and 𝜇𝑖𝑗 ∕= 𝜇𝑖+1,𝑗 for all 𝑗 = 1, . . . , 𝑛 and 𝑖 = 1, . . . , 𝑛𝑗 −1,
i.e. no two subsequent operations of a job are processed on the same machine
(otherwise the two operations may be replaced by one operation). Such a
job-shop is also called a job-shop without machine repetition. In the classic
formulation there is sufficient buffer space between the machines to store a job
if it finishes on one machine and the next machine is still occupied by another
job. A schedule is defined by the vector 𝑆 = (𝑆𝑖𝑗 ) of the starting times of
all operations 𝑂𝑖𝑗 . A schedule 𝑆 is feasible if: (i) 𝑆𝑖𝑗 + 𝑝𝑖𝑗 ≤ 𝑆𝑖+1,𝑗 for all
operations (precedence constraints between operations of the same job), and
(ii) 𝑆𝑖𝑗 + 𝑝𝑖𝑗 ≤ 𝑆𝑢𝑣 or 𝑆𝑢𝑣 + 𝑝𝑢𝑣 ≤ 𝑆𝑖𝑗 for all pairs 𝑂𝑖𝑗 , 𝑂𝑢𝑣 of operations with
𝜇𝑖𝑗 = 𝜇𝑢𝑣 , (each machine processes only one job at a time). The objective is
to determine a feasible schedule 𝑆 such that the makespan 𝐶𝑚𝑎𝑥 = max𝑛𝑗=1 𝐶𝑗 ,
where 𝐶𝑗 = 𝑆𝑛𝑗 ,𝑗 + 𝑝𝑛𝑗 ,𝑗 is the completion time of job 𝐽𝑗 .
A feasible schedule 𝑆 defines for each machine 𝑀𝑘 a sequencing 𝜋𝑘 =
(𝜋𝑘 (1), . . . , 𝜋𝑘 (𝑚𝑘 )) of the 𝑚𝑘 operations that has to be processed on 𝑀𝑘 .
Model
A job shop can be represented by a so-called disjunctive graph, introduced by
Roy and Sussman in 1964 [43]. A disjunctive graph 𝒢 = (𝑉, 𝐶, 𝐷) is a mixed
graph where 𝑉 is the set of nodes, 𝐶 a set of directed arcs (conjunctions) and
𝐷 a set of undirected arcs (disjunctions). In our case each node in 𝑉 represents
an operation (including two dummy operations 𝑠𝑡𝑎𝑟𝑡 and 𝑒𝑛𝑑, one preceding
and one following all operations. each arc in 𝐶 represents a precedence con-
straint between two consecutive operations of the same job; finally, for each
pair of operations which have to be processed on the same machine, there is
an undirected arc in 𝐷 representing the two possible precedence relations be-
tween the two operations. Nodes in 𝑉 are weighted with the processing time
of corresponding operations. For ease of notation operations can be indicated
with index 𝑖, the corresponding job with 𝐽(𝑖) and the corresponding machine
with 𝜇(𝑖), with 𝑖 = 1, . . . , 𝑛𝑜 , with 𝑛𝑜 being the number of operations.
With the disjunctive graph representation, the problem of finding a feasible
schedule for the job-shop problem is equivalent to the problem of fixing a
direction for each disjunction such that the corresponding graph is acyclic. A
set 𝒮 of fixed disjunctions is called a selection. A selection 𝒮 is called complete
if a direction has been fixed for each disjunction in 𝐷; moreover, 𝒮 is called

consistent if the corresponding graph 𝒢(𝒮) = (𝑉, 𝐶 ∪ 𝒮) is acyclic. Given a
complete consistent selection 𝒮, a corresponding feasible earliest start schedule
can be easily calculated. Denoted with 𝑟𝑖 the length of a longest path from
𝑠𝑡𝑎𝑟𝑡 to 𝑖 in 𝒢(𝒮), where the length of a path is defined as the sum of the
weights of all nodes on the path, node 𝑖 excluded, this feasible earliest start
schedule can be calculated by setting 𝑆𝑖 = 𝑟𝑖 . Therefore, makespan 𝐶𝑚𝑎𝑥 (𝑆) of
schedule 𝑆 is equal to the length 𝑟𝑒𝑛𝑑 of a longest path from 𝑠𝑡𝑎𝑟𝑡 to 𝑒𝑛𝑑. Vice
versa, for each schedule 𝑆, there is an associated complete consistent selection
𝒮; the feasible earliest start schedule corresponding to 𝒮 is not worse than 𝑆
in terms of a regular objective functions, so only complete consistent selections
may be considered.
Heuristic and meta-heuristics: local search and tabu search

Among the most effective algorithms for solving JSSP there is Tabu Search
algorithm. Some definitions of problem-specific neighborhoods for local and
tabu search algorithms based on the disjunctive graph are presented next.
We have stated that only complete consistent selections may be considered.
A natural way to go from one complete selection 𝒮 to another selection 𝒮 ′ is
to reverse certain disjunctive arcs. A first neighborhood 𝑁𝑐𝑎 , introduced by
van Laarhoven et al. [52] may be defined by reversing critical arcs. In fact, as
they observed, re-sequencing consecutive jobs that are not on the longest path
from 𝑠𝑡𝑎𝑟𝑡 to 𝑒𝑛𝑑 cannot improve the makespan. More specifically, a neighbor
in 𝑁𝑐𝑎 (𝒮) is generated by a move that reverses one oriented disjunctive arc
(𝑖, 𝑗) ∈ 𝒮 on some critical path in 𝒢(𝒮) into the arc (𝑗, 𝑖). This neighborhood
has the property that all selections 𝒮 ′ ∈ 𝑁𝑐𝑎 (𝒮) are feasible. This can be proved
as follows. Assume to the contrary that a selection 𝒮 ′ ∈ 𝑁𝑐𝑎 (𝒮) is not feasible,
i.e. the graph 𝒢(𝒮 ′ ) contains a cycle. 𝒢(𝒮) is acyclic for hypothesis. Thus,
the reversed arc (𝑗, 𝑖) ∈ 𝒮 must be part of the cycle in 𝒢(𝒮 ′ ) implying that a
path from 𝑖 to 𝑗 in 𝒢(𝒮 ′ ) exists which consists of at least three operations 𝑖,ℎ,𝑗.
This path must also be contained in 𝒢(𝒮) and must be longer than the path
consisting of the single arc (𝑖, 𝑗) ∈ 𝒮 because all processing times are assumed
to be positive. Since this is a contradiction to the fact that the arc (𝑖, 𝑗) belongs
to a longest path in 𝒢(𝒮), the graph 𝒢(𝒮 ′ ) cannot be cyclic. In the case that
the neighborhood 𝑁𝑐𝑎 (𝒮) of a selection 𝒮 is empty, we may conclude that 𝒮 is
optimal. In fact, in this case the chosen critical path contains no disjunctive
arc, then it contains only conjunctive arcs which implies that 𝐶𝑚𝑎𝑥 (𝒮) is equal
to the total processing time of a job. Since this value is a lower bound for
the optimal makespan, 𝒮 must be optimal. Neighborhood 𝑁𝑐𝑎 is proved to

be not connected, but it is proved to be opt-connected, i.e. it guarantees the
reachability of an optimal solution.
A disadvantage of 𝑁𝑐𝑎 is that several neighbors 𝒮 ′ exist which do not im-
prove the makespan of 𝒮. In the following we introduce a more effective neigh-
borhood, based on concepts of blocks. If 𝑃 𝐶 is a critical path in 𝒢(𝒮), a
sequence 𝑖1 , . . . , 𝑖𝑘 of at least two successive operations on 𝑃 𝐶 is called a (ma-
chine) block if the operations of the sequence are processed consecutively on
the same machine, and enlarging the subsequence by one operation leads to a
subsequence which does not fulfill this property. A first resolution approach
based on blocks can be found in [17] for a single machine scheduling problem
with release dates and due dates, and later it was adopted for other problems,
including job shop [12, 35]. The following property has been proved in [17]:
Theorem 2.4.1 Let S be a complete consistent selection with makespan 𝐶𝑚𝑎𝑥 (𝒮)
and let 𝑃 𝐶 be a critical path in 𝒢(𝒮). If another complete consistent selection
𝒮 ′ with 𝐶𝑚𝑎𝑥 (𝒮 ′ ) < 𝐶𝑚𝑎𝑥 (𝒮) exists, then in 𝒮 ′ at least one operation of a block
𝐵 on 𝑃 𝐶 has to be processed before the first or after the last operation of 𝐵.
The proof of this property is based on the fact that if the first and the last
operation of each block remain the same, all permutations of the operations in
the inner parts of the blocks do not shorten the length of the critical path.
1
On the basis of this theorem, the following block shift neighborhood 𝑁𝑏𝑠 ,
used by Grabowski et al. [18] for flow-shop problem and later by Grabowski
1
and Wodecki [19] for job-shop problem, may be defined. 𝑁𝑏𝑠 (𝒮) contains all
′
feasible selections 𝒮 which can be obtained from 𝒮 by shifting an operation of
some block on a critical path to the beginning or the end of the block. Con-
sequently, in this neighborhood the orientation of several disjunctive arcs may
be changed. For this reason, feasibility of neighbor selections must explicitly
be stated because it is not automatically fulfilled as in 𝑁𝑐𝑎 . Since infeasible
moves are not allowed, it’s more probable that opt-connectivity is not satisfied,
in fact opt-connectivity of this neighborhood is still an open question.
2 1
An opt-connected neighborhood 𝑁𝑏𝑠 , extending 𝑁𝑏𝑠 , can be obtained by
allowing some additional moves. If a move of an operation to the beginning
[or the end] of a block is infeasible, then the operation is moved to the first
(last) position in the block such that the resulting selection is feasible. With
2 1
the inclusion in 𝑁𝑏𝑠 of these other moves than moves in 𝑁𝑏𝑠 , it can be proved
2 2
that neighborhood 𝑁𝑏𝑠 is opt-connected. Even for neighborhood 𝑁𝑏𝑠 , if the
2
neighborhood 𝑁𝑏𝑠 (𝒮) of a selection 𝒮 is empty, then 𝒮 is optimal.
1 2
A disadvantage of neighborhoods 𝑁𝑏𝑠 and 𝑁𝑏𝑠 is that they may be quite large.
2 1
For this reason a smaller neighborhood 𝑁𝑐𝑎 ⊆ (𝑁𝑐𝑎 ∩𝑁𝑏𝑠 ) was proposed [34, 36].
2 ′
𝑁𝑐𝑎 (𝒮) contains all selections 𝒮 which can be obtained from 𝒮 by interchang-
2
ing the first two or the last two operations of a block. Since 𝑁𝑐𝑎 (𝒮) is a subset
2
of 𝑁𝑐𝑎 (𝒮), all selections in 𝑁𝑐𝑎 are feasible. Furthermore, due to Theorem 2.4.1
all selections 𝒮 ′ ∈ 𝑁𝑐𝑎 (𝒮) − 𝑁𝑐𝑎
2
(𝒮) satisfy 𝐶𝑚𝑎𝑥 (𝒮 ′ ) ≥ 𝐶𝑚𝑎𝑥 (𝒮) since only op-
erations in the inner part of blocks are changed. Thus, only non-improving
2
solutions are excluded in the reduced neighborhood 𝑁𝑐𝑎 (𝒮).
Concerning neighborhood evaluation, in order to determine the best neigh-

bor for a given solution, two methods are possible: exact and approximate eval-
uation. Exact evaluation consists in calculating exactly the makespan while
approximate evaluation consists in calculating an estimate of the makespan,
that usually is a lower bound of the makespan. Exact evaluation is worth
when it does not take much computational time. In the job-shop case, due to
the fact that each operation has at most two predecessors (a job and a machine
predecessor), makespan can be calculated in 𝑂(𝑛𝑜 ) time by longest path cal-
culations where 𝑛𝑜 is the number of operations. However, this is not enough
to have acceptable computational times, because makespan calculation has to
be performed for all solution in the neighborhood. To reduce the computa-
tional time it is needed to prove some additional properties. In general, this is
possible for neighborhood obtained by not very disrupting moves (as 𝑁𝑐𝑎 and
2 1
𝑁𝑐𝑎 ); instead, for neighborhood obtained by more disrupting moves (as 𝑁𝑏𝑠
2
and 𝑁𝑏𝑠 ), an approximate evaluation is usually needed.
2
An important property for evaluating neighborhood 𝑁𝑐𝑎 has been proved
by Nowicki and Smutnicki [35]. This property is shown in the following, after
some notations. We have already noticed that a schedule can be specified
by a vector 𝜋 = (𝜋1 , . . . , 𝜋𝑚 ) where, for 𝑘 = 1, . . . , 𝑚, the sequence 𝜋𝑘 =
(𝜋𝑘 (1), . . . , 𝜋𝑘 (𝑚𝑘 )) defines the order in which all 𝑚𝑘 operations 𝑖 with 𝜇(𝑖) =
𝑀𝑘 are processed on 𝑀𝑘 . Let 𝒢(𝜋) be the directed graph corresponding to 𝜋; a
solution 𝜋 is feasible if and only if 𝒢(𝜋) contains no cycles. Let 𝜋 be a feasible
solution and let 𝜋 ′ be a neighbor of 𝜋 with respect to the neighborhood 𝑁𝑐𝑎 .
The solution 𝜋 ′ is derived from 𝜋 by reversing a critical oriented disjunctive
arc (𝑖, 𝑗) in 𝒢(𝜋). Let 𝜋 (𝑖,𝑗) be such a solution and, for a feasible schedule 𝜋
and operations 𝑢, 𝑣, let 𝒫𝜋 (𝑢 ∨ 𝑣) and 𝒫𝜋 (𝑢) be the set of all paths in 𝒢(𝜋)
containing nodes 𝑢 or 𝑣 and not containing 𝑢, respectively. Furthermore, let
𝒫𝜋 (𝑢∧𝑣) and 𝒫𝜋 (𝑢∧𝑣) denote the set of all paths in 𝒢(𝜋) not containing nodes
𝑢 and 𝑣 and not containing 𝑢 but containing 𝑣, respectively. For a given set of
paths 𝒫 the length of a longest path in 𝒫 is denoted by 𝑙(𝒫). The following
property has been proved [35]:

Property 2.4.1 The makespan of a solution 𝜋 ′ := 𝜋 (𝑖,𝑗) ∈ 𝑁𝑐𝑎 (𝜋) is given by
𝐶𝑚𝑎𝑥 (𝜋 ′ ) = max{𝑙(𝒫𝜋′ (𝑖 ∨ 𝑗)), 𝒫𝜋 (𝑖)}
Property 2.4.1 avoid to consider other paths for calculating the makespan
exactly; moreover it has been shown that it can be evaluated in an efficient
way, obtaining a further reduction of computational time.
Flow shop
The flow shop problem is special case of job shop, in which:
∙ each job 𝐽𝑗 consists of 𝑚 operations 𝑂𝑖𝑗 with processing times 𝑝𝑖𝑗 (𝑖 =
1, . . . , 𝑚) where 𝑂𝑖𝑗 must be processed on machine 𝑀𝑖 ;
∙ there are precedence constraints of the form 𝑂𝑖𝑗 → 𝑂𝑖+1,𝑗 (𝑖 = 1, . . . , 𝑚−
1), and 𝜇𝑖𝑗 = 𝑀𝑖 (𝑖 = 1, . . . , 𝑚), for each 𝑗 = 1, . . . , 𝑛, i.e. all jobs are
processed on machines in the same order.
Thus, the problem is to find machine orders, i.e. orders of jobs to be
processed on the same machine. Among problems with arbitrary processing
times 𝑝𝑖𝑗 , problem 𝐹 2∣∣𝐶𝑚𝑎𝑥 is the only flow shop problem which has been
polynomially solved.
Open shop
The open shop problem is a shop problem more general than job-shop and
flow-shop, in which:
∙ each job 𝐽𝑗 consists of 𝑚 operations 𝑂𝑖𝑗 (𝑖 = 1, . . . , 𝑚) where 𝑂𝑖𝑗 must
be processed on machine 𝑀𝑖 , and
∙ there are no precedence relations between the operations.
Thus, the problem is to find job orders (orders of operations of the same
job) and machine orders (orders of operations to be processed on the same
machine).
Among problems with arbitrary processing times 𝑝𝑖𝑗 and no preemption,
only the problem with two machines 𝑂2∣∣𝐶𝑚𝑎𝑥 (or symmetrically the problem
with two jobs 𝑂∣𝑛 = 2∣𝐶𝑚𝑎𝑥 ) has been polynomially solved (in 𝑂(𝑛) time).
Instead, for various problems with unitary processing time, polynomial algo-
rithms have been found.
2.5 Generalized shop scheduling problems

Various generalizations of shop problems can be found in literature. Some
among the most studied are presented next. We refer to generalizations of
job-shop, but similar considerations can be done for open-shop and flow-shop
Time-lags
Time-lags are general timing constraints between the starting times of opera-
tions. They can be introduced by the start-start relations 𝑆𝑖 + 𝑑𝑖𝑗 ≤ 𝑆𝑗 where
𝑑𝑖𝑗 is an arbitrary integer number.
Time-lags 𝑑𝑖𝑗 may be incorporated into the disjunctive graph 𝒢 = (𝑉, 𝐶, 𝐷)
by weighing the conjunctive arcs 𝑖 → 𝑗 ∈ 𝐶 with the distances 𝑑𝑖𝑗 and the
disjunctive arcs 𝑖 − 𝑗 ∈ 𝐷 with the pairs (𝑑𝑖𝑗 , 𝑑𝑗𝑖 ): when an orientation is
chosen, the arc is weighed with 𝑑𝑖𝑗 or 𝑑𝑗𝑖 if it is oriented into the direction
(𝑖, 𝑗) or (𝑗, 𝑖), respectively. Time-lags may for example be used to model the
following constraints:
∙ Release times and deadlines: denoted with 𝑟𝑖 a release time and with
𝐷𝑖 a deadline for operation 𝑖, then the conditions 𝑆𝑠𝑡𝑎𝑟𝑡 + 𝑟𝑖 ≤ 𝑆𝑖 and
𝑆𝑖 + 𝑝𝑖 − 𝐷𝑖 ≤ 𝑆𝑠𝑡𝑎𝑟𝑡 with 𝑆𝑠𝑡𝑎𝑟𝑡 = 0 must be hold. Thus, release
times and deadlines can be modeled by the time-lags 𝑑𝑠𝑡𝑎𝑟𝑡,𝑖 := 𝑟𝑖 and
𝑑𝑖,𝑠𝑡𝑎𝑟𝑡 := 𝑝𝑖 − 𝐷𝑖
∙ Exact relative timing: if an operation 𝑗 must start exactly 𝑙𝑖𝑗 time units
after the completion of operation 𝑖, then the relation 𝑆𝑖 + 𝑝𝑖 + 𝑙𝑖𝑗 = 𝑆𝑗
must be hold, with time-lag 𝑑𝑖𝑗 = 𝑝𝑖 + 𝑙𝑖𝑗
∙ Setup times: if a setup time is needed between the completion of an
operation 𝑖 and the beginning of operation 𝑗 on the same machine, one
of the two relations 𝑆𝑖 + 𝑝𝑖 + 𝑠𝑖𝑗 ≤ 𝑆𝑗 and 𝑆𝑗 + 𝑝𝑗 + 𝑠𝑗𝑖 ≤ 𝑆𝑖 must be
hold, where 𝑠𝑖𝑗 denotes the setup time between operations 𝑖 and 𝑗.
∙ Machine unavailabilities: if a machine 𝑀𝑘 is unavailable within time
intervals ]𝑎𝑢 , 𝑏𝑢 [ for 𝑢 = 1, . . . , 𝑣, we may introduce 𝑣 artificial operations
𝑢 = 1, . . . , 𝑣 with 𝜇(𝑢) = 𝑀𝑘 , processing times 𝑝𝑢 := 𝑏𝑢 −𝑎𝑢 , release times
𝑟𝑢 := 𝑎𝑢 and deadlines 𝐷𝑢 := 𝑏𝑢 . Then, release times and deadlines can
be modeled with time-lags as above
∙ Maximum lateness objective: problems with maximum lateness objective
𝐿𝑚𝑎𝑥 = max𝑛𝑗=1 𝐶𝑗 − 𝑑𝑗 can be reduced to 𝐶𝑚𝑎𝑥 problems by setting
𝑑𝑙(𝑗),𝑒𝑛𝑑 = 𝑝𝑙(𝑗) − 𝑑𝑗 for each job 𝑗 where 𝑙(𝑗) denotes the last operation
of job 𝑗
Blocking
Another generalization concerns blocking operations. A blocking operation is
an operation that remains on its processing machine 𝑀𝑘 and blocks it when it
has finished on it and the next machine where the corresponding job has to be
processed is still occupied by another job: 𝑀𝑘 remains blocked until the next
machine is available. This situation can arise when jobs can not be parked in
wait outside the machine (for example in a so-called buffer). A JSSP where all
operations are blocking is called Blocking Job Shop Scheduling Problem.
Consider two blocking operations 𝑖 and 𝑗 which have to be processed on the
same machine 𝜇(𝑖) = 𝜇(𝑗). If operation 𝑖 precedes operation 𝑗, the successor
operation 𝛿(𝑖) of operation 𝑖 must start before operation 𝑗 in order to unblock
the machine, i.e. we must have 𝑆𝛿(𝑖) ≤ 𝑆𝑗 . On the other hand,, if operation
𝑗 precedes operation 𝑖, then operation 𝛿(𝑗) must start before operation 𝑖, i.e.
we must have 𝑆𝛿(𝑗) ≤ 𝑆𝑖 . Thus, there are two mutually exclusive (alternative)
relations in connection with 𝑖 and 𝑗. These relations can be modeled by a pair
of alternative arcs (𝛿(𝑖), 𝑗) and (𝛿(𝑗), 𝑖) with arc weights 𝑤𝛿(𝑖),𝑗 = 𝑤𝛿(𝑗),𝑖 =
0. In order to get a feasible schedule, exactly one of the two alternatives
has to be chosen (selected). Note that choosing (𝛿(𝑖), 𝑗) implies that 𝑖 must
precede 𝑗 by transitivity, and choosing (𝛿(𝑗), 𝑖) implies that 𝑗 must precede
𝑖. Thus, if blocking arcs (𝛿(𝑖), 𝑗), (𝛿(𝑗), 𝑖) are introduced, there is no need to
add disjunctive arcs (𝑖, 𝑗), (𝑗, 𝑖) between operations which are processed on the
same machine 𝜇(𝑖) = 𝜇(𝑗). Similar considerations can be done in the case in
which only one between 𝑖 and 𝑗 is a blocking operation, and in the case in which
neither 𝑖 nor 𝑗 are blocking operations, with the only observation that, when no
blocking arc is added between 𝛿(𝑖) and 𝑗 [or between 𝛿(𝑗) and 𝑖], disjunctive arc
(𝑖, 𝑗) [(𝑗, 𝑖)] is not deleted; in this case the disjunction between (𝑖, 𝑗) [(𝑗, 𝑖)] can
assume the form (𝑆𝑖 + 𝑤𝑖𝑗 ≤ 𝑆𝑗 ) [(𝑆𝑗 + 𝑤𝑗𝑖 ≤ 𝑆𝑖 ) where 𝑤𝑖𝑗 = 𝑝𝑖 [𝑤𝑗𝑖 = 𝑝𝑗 ]. In
the special case in which operation 𝑖 is the last operation of job 𝐽(𝑖), machine
𝜇(𝑖) is not blocked after the processing of 𝑖, so, in this case, operation 𝑖 is
always assumed to be non-blocking.
Summarizing that, to represent the whole problem, we can introduce a set
𝐴 of pairs of alternative arcs {(𝑖, 𝑗), (𝑓, 𝑔)} corresponding to mutually exclusive
pairs of relations (𝑆𝑖 + 𝑤𝑖𝑗 ≤ 𝑆𝑗 ) or (𝑆𝑓 + 𝑤𝑓 𝑔 ≤ 𝑆𝑔 ). The resulting graph
𝐺 = (𝑉, 𝐶, 𝐴) is called alternative graph [28, 29]. Similarly as in the disjunctive
graph model we have to determine a selection 𝒮 which contains exactly one
arc (𝑖, 𝑗) or (𝑓, 𝑔) for each pair of alternative arcs in 𝐴 such that the resulting
graph 𝒢(𝒮) = (𝑉, 𝐶 ∪ 𝑆) with arc weights 𝑤 does not contain a positive cycle.
Flexible Job Shop

Flexible Job Shop Scheduling Problems are problems where machine are flex-
ible, i.e. operations can be performed non only by a one machine by a subset
of machines (multipurpose machines).
Problem formulation
Differently from the classic formulation, in FJSSP, a set of machines ℳ𝑖 ⊆
ℳ that can process operation 𝑖, is associated to operation 𝑖. If operation 𝑖
is executed on machine 𝑀𝑘 ∈ ℳ𝑖 , then its processing time is equal to 𝑝𝑖𝑘 .
Hence, a further decision in FJSSP with respect to JSSP is to assign to each
operation 𝑖 a machine from the machine set ℳ𝑖 ; the objective function is
the 𝐶𝑚𝑎𝑥 minimization. Once a machine is assigned to each operation, the
problem reduce to classic JSSP. A typical application of FJSSP can be found in
manufacturing scheduling when the operations need certain tools for processing
and the machines are only equipped with a few of them. Then ℳ𝑖 denotes all
machines equipped with the tools needed by operation 𝑖.
Neighborhoods for local and tabu search

In the following we assume that a machine assignment 𝜇 (where 𝜇(𝑖) ∈ ℳ𝑖
denotes the machine assigned to operation 𝑖) is given; also a corresponding
complete consistent selection 𝒮, with the associated earliest start schedule 𝑆,
is given.
A first kind of neighborhood ([23]) is a natural extension for this problem
1 2
of the block shift neighborhoods 𝒩𝑏𝑠 and 𝒩𝑏𝑠 for the classic job-shop problem
as defined in Section 2.4. The definition of these neighborhood is based on the
following theorem:
Let (𝜇, 𝒮) be a feasible solution with makespan 𝐶𝑚𝑎𝑥 (𝒮) and let 𝑃 𝐶 be a
critical path in 𝒢(𝒮). If another feasible solution (𝜇′ , 𝒮 ′ ) with 𝐶𝑚𝑎𝑥
′
< 𝐶𝑚𝑎𝑥
exists, then:
∙ in 𝜇′ at least one critical operation on 𝑃 𝐶 has to be assigned to another
machine, or
∙ in 𝒮 ′ at least one operation of some block 𝐵 on 𝑃 𝐶 has to be processed
before the first or after the last operation of 𝐵.
1 2
Substantially, on the basis of this theorem, neighborhoods 𝒩𝑏𝑠 and 𝒩𝑏𝑠 can
be extended by considering movement of critical operation from a machine to a
certain position in another machine. Again, it can be shown that the enlarged
2
neighborhood 𝑁𝑏𝑠 is opt-connected.
A disadvantage of these neighborhoods is that they may be quite large
since each critical operation may be moved to a large number of positions
on other machines. The number of moves may be reduced by allowing only
feasible moves and trying to calculate the best insertion position of an operation
which is assigned to another machine (i.e. all other insertions of this operation
on the same machine do not lead to schedules with a better makespan). In
the following, let 𝜋1 , . . . , 𝜋𝑚 be the machine sequences corresponding to the
solution (𝜇, 𝒮) and let 𝑣 be a given operation and 𝑀𝑘 ∈ ℳ a given machine
(that hereinafter we will identify with its index 𝑘 for ease of notation). A move
that removes 𝑣 from its machine sequence 𝜋𝜇(𝑣) and insert it into the machine
sequence 𝜋𝑘 on 𝑀𝑘 (if 𝑀𝑘 ∈ ℳ(𝑣)) is called 𝑘-insertion. A 𝑘-insertion is called
feasible if the resulting disjunctive graph is acyclic; a feasible 𝑘-insertion (of v)
is called optimal if the makespan of the resulting solution is not larger than the
makespan of any other solution which is obtained by a feasible 𝑘-insertion (of
v). A reduced neighborhood which always contains a solution corresponding to
an optimal 𝑘-insertion has been used in [30] by Mastrolilli and Gambardella.
Job-Shop Problems with Transport Times

Transportation time can be taken into account in an other generalization of
JSSP. When a job is moved from one machine 𝑀𝑘 to the next one, say 𝑀𝑙 ,
where it has to be processed, a transportation time 𝑡𝑗𝑘𝑙 is required. These
transportation times may be job dependent or job-independent. In this for-
mulation we assume that the transportation is done by transport robots which
can handle at most one job at a time. We again assume that unlimited buffer
space exists between the machines, where jobs processed and waiting for a robot
may be stored. No further time for the transfer from machine to its buffer is
considered. Similarly, each machine has an unlimited input buffer where jobs
which have been transported can wait for processing. We assume that trans-
portation times satisfy the following triangle inequality for all jobs 𝐽𝑗 and all
machines 𝑀𝑘 ,𝑀𝑙 ,𝑀ℎ : 𝑡𝑗𝑘ℎ + 𝑡𝑗ℎ𝑙 ≥ 𝑡𝑗𝑘𝑙 . We assume that there is a set ℛ of
𝑟 identical transport robots 𝑅1 , . . . , 𝑅𝑟 and each job can be transported by
any of these robots. Then following two cases can be distinguished, given the
number of jobs 𝑛: (i) an unlimited number of robots 𝑟 ≥ 𝑛 and (ii) a limited
number of robots 𝑟 < 𝑛. In the first case no conflicts arise between two jobs
requesting for the same vehicle; in the second case, robots are resources with
limited capacity as machines, so their assignment to jobs has to be decided. In
a further generalization of this model,robots may be nonidentical and may have
different characteristics (so-called multi-purpose robots). As for multi-purpose
machines, this similar situation is modeled by associating with each job 𝐽𝑗 a
set ℛ𝑗 ⊆ ℛ containing all robots by which 𝐽𝑗 can be transported.
General shop problems with machine dependent removal and

setup times
In general shop problems, we may have removal and setup, needed to remove
a tool from a machine and to setup a different tool in it. In this case we have
a partition of the set 𝐼 = {1, . . . , 𝑛𝑜 } of operations of all jobs into disjoint sets
𝐼1 , . . . , 𝐼𝑟 , called groups. For any two operations 𝑖,𝑗, with 𝑖 ∈ 𝐼ℎ and 𝑗 ∈ 𝐼𝑙 , that
have to be processed on the same machine 𝑀𝑘 , operation 𝑗 can not be started
until 𝑔ℎ𝑙𝑘 +𝑓ℎ𝑙𝑘 time units after the completion time of operation 𝑖, or operation
𝑖 can not be started until 𝑔𝑙ℎ𝑘 + 𝑓𝑙ℎ𝑘 time units after the completion time of
operation 𝑗; 𝑔ℎ𝑙𝑘 and 𝑓ℎ𝑙𝑘 are the removal and the setup time, respectively.
The changeover times, from operation 𝑖 to operation 𝑗 and from operation 𝑗 to
operation 𝑖, can be represented in the disjunctive graph model by weighing the
corresponding disjunctive arcs, (𝑖, 𝑗) and (𝑗, 𝑖), with 𝑔ℎ𝑙𝑘 + 𝑓ℎ𝑙𝑘 and 𝑔𝑙ℎ𝑘 + 𝑓𝑙ℎ𝑘 ,
respectively.
2.6 Multi-resource constrained scheduling problems

The resource-constrained project scheduling problem (RCPSP) is a very general
scheduling problem which may be used to model many applications not only in
manufacturing area but in other areas like services. In fact it takes into account
scarcity of resources, that is a typical constraint of real application problems.
The objective is to schedule some activities over time such that some scarce
resource capacities are respected and a certain objective function is optimized.
The problem may be formulated as follows: 𝑛 activities 𝑖 = 1, . . . , 𝑛, require,
to be processed, a constant amount 𝑟𝑖𝑘 of renewable resource 𝑘 with 𝑘 =
1, . . . , 𝑟. A constant amount 𝑅𝑘 of resource 𝑘 is available at any time. Activity
𝑖 occupies its necessary resources for a time period equal to its processing time
𝑝𝑖 . Precedence constraints are defined between some activities. The objective
is to determine a feasible vector of starting times 𝑆 = {𝑆1 , . . . , 𝑆𝑛 } for the
activities 𝑖 = 1, . . . , 𝑛 such that the objective function is optimized. A solution
𝑆 is feasible if the following three conditions are satisfied: (i) at each time 𝑡 the
total resource demand is less than or equal to the resource availability 𝑅𝑘 of
each resource 𝑘 = 1, . . . , 𝑟, (ii) the given precedence constraints are respected,
i.e. 𝑆𝑖 + 𝑝𝑖 ≤ 𝑆𝑗 if 𝑖 precedes 𝑗.
It is useful, for the RCPSP, to represent the structure of a project by a
so-called activity-on-node network 𝒢 = (𝑉, 𝐴), where the vertex set 𝑉 :=
{𝑠𝑡𝑎𝑟𝑡, 1, ..., 𝑛, 𝑒𝑛𝑑} contains all activities plus two dummy ones correspond-
ing to the start and the end of the project, and the set of arcs 𝐴 = {(𝑖, 𝑗)∣𝑖, 𝑗 ∈
𝑉 ; 𝑖 → 𝑗} represents the precedence constraints. Each vertex 𝑖 ∈ 𝑉 is weighed
with the corresponding processing time 𝑝𝑖 . Another less used representation
of projects is based on so-called activity-on-arc networks where each activity
is modeled by an arc.
Local search and tabu search

Some neighborhood definition for local and tabu search algorithms for RCPSP
are presented next. Reviews and comparisons of other different heuristics can
be found in Hartmann and Kolisch [22] and in Kolisch and Hartmann [25, 26].
The generic solution is represented by a sequences of the activities, the activity
list 𝐿.
∙ The adjacent pairwise interchange-neighborhood. This neighbor-

hood is generated by a move, defined on activitiy 𝑖𝜆 for 𝜆 = 1, . . . , 𝑛 − 1,
that interchanges the elements 𝑖 and its successor in 𝐿, 𝑖𝜆+1 . This move
leads to a feasible list if no precedence relation 𝑖𝜆 → 𝑖𝜆+1 exists. Since we
have at most 𝑛 − 1 feasible moves for a list, the size of the neighborhood
is bounded by 𝑂(𝑛).
∙ Swap-neighborhood. The swap-neighborhood generalizes the adjacent
pairwise interchange-neighborhood and is generated by a move defined on
two activities 𝑖𝜆 and 𝑖𝜇 for 𝜆, 𝜇 = 1, . . . , 𝑛 with 𝜆 < 𝜇, that interchanges
the elements 𝑖𝜆 and 𝑖𝜇 in L. Such move is only feasible if for all 𝜈 =
{𝜆 + 1, . . . , 𝜇 − 1} no precedence relation 𝑖𝜆 → 𝑖𝜈 or 𝑖𝜈 → 𝑖𝜇 exists.
Since we have at most 𝑛(𝑛 − 1)/2 feasible moves for a list, the size of the
neighborhood is bounded by 𝑂(𝑛2 ).
∙ Shift-neighborhood. The shift-neighborhood also generalizes the ad-
jacent pairwise interchange-neighborhood and is generated by a move
defined on an activities 𝑖𝜆 and an index 𝜇 for 𝜆, 𝜇 = 1, . . . , 𝑛, with 𝜆 ∕= 𝜇,
that shifts the element 𝑖𝜆 in position 𝜇 in L. For 𝜆 < 𝜇 we have a right
shift, symmetrically, for 𝜆 > 𝜇 we have a left shift. Such shifts are only
feasible if for 𝜈 = {𝜆 + 1, . . . , 𝜇} no precedence relation 𝑖𝜆 → 𝑖𝜈 and
for 𝜈 = {𝜇, . . . , 𝜆 − 1} no precedence relation 𝑖𝜈 → 𝑖𝜆 exists. Since we
have at most 𝑛(𝑛 − 1)/2 feasible shift-operators for a list, the size of this
neighborhood is bounded by 𝑂(𝑛2 ).
Chapter 3
Case study 1: A Tabu Search

algorithm for production
scheduling in packaging
department
In this chapter, we address the problem of scheduling packaging operations

in Packaging department of a real pharmaceutical plant. A detailed graph has
been needed to model the problem for its resolution with a tabu search algorithm.
This case study shows that scheduling technology is nowadays mature to solve
production and, in general, practical scheduling problems.
3.1 Introduction
In this chapter we take into account a real case study of production schedul-
ing in a pharmaceutical industry, in the specific, in its packaging department.
Previous attempts to design a computerized tool for production scheduling at
this department have had limited success, and similar performance has been
observed in practice for many computerized tools for planning and scheduling
[31, 32]. A common reason for this behavior is that the models adopted by
computerized systems suffer from excessive simplification and do not incorpo-
rate all the relevant aspects of the shop floor [54]. On the other hands, example
The problem can be formulated as a multi-purpose machine scheduling problem
[51] with additional constraints related to the availability of tools and opera-
26
CHAPTER 3. CASE STUDY 1: A TABU SEARCH ALGORITHM FOR
PRODUCTION SCHEDULING IN PACKAGING DEPARTMENT 27
tors, removal and setup times, release times, due dates and deadlines. The
objectives are the joint minimization of makespan and maximum tardiness,
which are addressed in lexicographic order. To the best of our knowledge, no
published work addresses exactly the problem studied in this chapter, even
though many algorithms have been proposed to solve relaxations of this prob-
lem, addressing different subsets of constraints. Among the others, we cite the
parallel machine scheduling problems with setup and removal times, release
and due dates [48], the vehicle routing problem with fixed number of vehicles
and time windows [3, 4, 9] and the resource constrained scheduling problem [6].
The remainder of this chapter is organized as follows. In Section 3.2 a

detailed description of the problem is given. A graph representation of the
problem is then presented in Section 3.3 and a Tabu Search algorithm proposed
in 3.4. Finally, in Section 3.5 we report on our computational experiments,
carried on real industrial instances and on randomly generated instances, giving
some final comments in Section 3.6
3.2 Description of the problem

The packaging department is described in Section 1.2 and in [53]. It contains
three packaging lines working in parallel, each of which performs, on a single
lot, all operations from the production of blisters to the final individual specific
packages. Therefore, from a scheduling point of view, a line acts as a single
machine and a single lot can be considered as a single job. a descriptive model
of the problem is given in the following.
Machine unavailability can be viewed as a special job characterized by a release
date, corresponding to its starting time, a processing time, corresponding to
its duration, and a deadline corresponding to its finish time. Each mainte-
nance operation must be executed on the prescribed machine while the lack of
operators can be moved from a machine to another.
Given the description in 1.2 and the considerations above, we report below
the three-fields classification scheme of Graham for this scheduling problem:
𝑂𝑀 𝑃 𝑀 ∣𝑟𝑖 , 𝑑𝑖 , 𝐷𝑖 , 𝑅𝑠𝑑 , 𝑆𝑠𝑑 , 𝑢𝑛𝑎𝑣𝑎𝑖𝑙𝑗 ∣𝐿𝑒𝑥(𝐶𝑚𝑎𝑥 , 𝑇𝑚𝑎𝑥 )
Concerning the shop environment, 𝑂𝑀 𝑃 𝑀 is the Open shop Multi-Purpose

Machines. In fact, the department contains parallel machines but each job has
its own set of machines and tools on which it can be processed and has to
be assigned to one machine and one tool in its sets. Then the jobs assigned
to the same tool or machine must be sequenced. Viewing the jobs assigned
to the same tool as operations of an extended job, the sequencing part of the
problem is similar to an open shop problem. Instead, for what concerns the
constraints of the problem, we have the presence of release times, due dates and
deadlines (𝑟𝑖 , 𝑑𝑖 , 𝐷𝑖 , respectively). 𝑅𝑠𝑑 and 𝑆𝑠𝑑 indicate sequence-dependent
removal times and sequence-dependent setup times. Moreover, resources (ma-
chines and operators) are not available all the time but only during well defined
periods (𝑢𝑛𝑎𝑣𝑎𝑖𝑙𝑗 ). Specifically, in our case job processing is resumable, i.e.,
can be interrupted when the machine or the operators become unavailable and
resumed later (but no other job can be processed in between). Setups and
removals are not resumable, i.e., they cannot be started if unavailability arise
before completion. The optimality criteria of the problem is 𝐿𝑒𝑥(𝐶𝑚𝑎𝑥 , 𝑇𝑚𝑎𝑥 ),
i.e. the minimization of makespan and maximum tardiness in lexicographic
order.
We notice that, in the scheduling literature, even relaxed versions of this
problem, such as the vehicle routing problem with release and due dates, are
considered particularly difficult NP-hard problems [40]. Moreover, some con-
straints, such as the resumable unavailability of resources, are not frequently
addressed in scheduling literature, at least in combination with others.
3.3 Graph representation of a solution

In this section, we introduce the notation used throughout the chapter and
then we formally describe the constraints satisfied by feasible solutions.
Problem data consist of the following. A set of 𝑛 jobs 𝒥 = {1, 2, ..., 𝑛},
each consisting of a single operation, must be scheduled on a set of 𝑚 machines
ℳ = {1, 2, ..., 𝑚}. Each job must be processed entirely on the same machine,
which can process at most one job at a time. We denote with ℳ𝑗 ⊆ ℳ the
set of machines compatible with job 𝑗, i.e. able to process 𝑗. To process job
𝑗, a machine must be equipped with a fixed number 𝑏 of operators and with a
tool 𝑇𝑗 , chosen in the set of tools 𝒯 = {1, 2, ..., 𝑡}. We denote with 𝒯𝑗 ⊆ 𝒯 the
set of tools compatible with job 𝑗. Also, let 𝑝𝑗 , 𝑟𝑗 , 𝑑𝑗 and 𝑑˜𝑗 be the processing
time, release date, due date and deadline of job 𝑗, respectively.
A given removal time 𝑔𝑖𝑗 is required, between two jobs 𝑖 and 𝑗 processed
consecutively on the same machine, to clean and calibrate the machine and to
remove tool 𝑇𝑖 if 𝑖 and 𝑗 use different tools. If 𝑇𝑖 ∕= 𝑇𝑗 an additional setup time
𝑓𝑖𝑗 is required after 𝑔𝑖𝑗 to set up the new tool 𝑇𝑗 . A similar situation occurs if
job 𝑖 is processed on machine ℎ′ , job 𝑗 is processed on machine ℎ and both use
consecutively the same tool. Letting 𝛽(𝑖) the job sequenced after 𝑖 on machine
ℎ′ and 𝛼(𝑗) the job preceding 𝑗 on machine ℎ, a removal time 𝑔𝑖𝛽(𝑖) is required
to remove the tool from ℎ′ and a setup 𝑓𝛼(𝑗)𝑗 is required to set up the tool on
ℎ. All setup/removal times satisfy the triangular inequality, i.e., 𝑓𝑖𝑗 + 𝑓𝑗𝑘 ≥ 𝑓𝑖𝑘
and 𝑔𝑖𝑗 + 𝑔𝑗𝑘 ≥ 𝑔𝑖𝑘 .
The number 𝑜𝑖 of operators available during shift 𝑖 = 1, . . . , 𝑠 is known in
advance, and operators must be assigned ⌊ ⌋ to the machines for the entire du-
ration of a shift. Therefore, at most 𝑜𝑏𝑖 machines ⌊ can
⌋ be active during shift
𝑖. We model this situation by introducing 𝑚 − 𝑜𝑏𝑖 dummy jobs called un-
availabilities, with release date, deadline and processing time equal to the shift
start, completion and duration, respectively. These jobs will be scheduled on
the machines with all the other jobs. In some cases, the subset of inactive ma-
chines for a shift is partially specified in advance, for example when preventive
maintenance operations are planned for some machines during that shift.
We denote with (𝒰 = {(𝑛 + 1), . . . , (𝑛 + 𝑞)} the set of all unavailabilities,
∑ ⌊𝑜 ⌋)
with 𝑞 = 𝑖=1,...,𝑠 𝑚 − 𝑏 , and with ℳ𝑢 ⊆ ℳ the set of the machines
𝑖
compatible with unavailability 𝑢 ∈ 𝒰.

Finding a schedule consists of solving five subproblems. We postpone the
feasibility issue to the end of this section.
(𝑖) Assign each job 𝑗 ∈ 𝒥 to a machine ℎ ∈ ℳ𝑗 . Let 𝒥 𝑀 (ℎ) be the set of

jobs assigned to machine ℎ = 1, . . . , 𝑚.
(𝑖𝑖) Assign each job 𝑗 ∈ 𝒥 to a tool 𝑘 ∈ 𝒯𝑗 . Let 𝒥 𝑇 (𝑘) be the set of jobs
assigned to tool 𝑘 = 1, . . . , 𝑡.
(𝑖𝑖𝑖) Assign each unavailability 𝑢 ∈ 𝒰 to a machine ℎ ∈ ℳ𝑢 such that unavail-
abilities assigned to the same machine are non-overlapping. Let 𝒰(ℎ) be
the set of unavailabilities assigned to machine ℎ = 1, . . . , 𝑚, and 𝜇 be the
𝑚-tuple 𝒰(1), 𝒰(2), . . . , 𝒰(𝑚).
(𝑖𝑣) Sequence the jobs in 𝒥 𝑀 (ℎ), ℎ = 1, . . . , 𝑚 and the jobs in 𝒥 𝑇 (𝑘), 𝑘 =
1, . . . , 𝑡. Let 𝜎ℎ be the resulting sequence on machine h and 𝜋𝑘 be the
resulting sequence on tool k. Let also 𝜎 be the 𝑚-tuple 𝜎1 , 𝜎2 , . . . , 𝜎𝑚
and 𝜋 be the 𝑡-tuple 𝜋1 , 𝜋2 , . . . , 𝜋𝑡 .
(𝑣) Define a schedule, i.e., a starting time 𝑆𝑗 and a completion time 𝐶𝑗 ≤
𝑑˜𝑗 for each job 𝑗 ∈ 𝒥 such that each machine processes at most one
job/unavailability at a time. Let 𝑆 and 𝐶 be the vectors of start-
ing/completion time of all jobs, 𝑆 = (𝑆1 , 𝑆2 , . . . , 𝑆𝑛 ), 𝐶 = (𝐶1 , 𝐶2 , . . . , 𝐶𝑛 ).
Let a solution 𝐻 denote the triple 𝐻 = (𝜇, 𝜎, 𝜋), i.e., the output of sub-
problems (𝑖) − (𝑖𝑣), and let a schedule denote the pair (𝑆, 𝐶). For each job
𝑗 ∈ 𝒥 𝑀 (ℎ) we denote with 𝛼(𝑗) the job preceding 𝑗 in 𝜎ℎ and with 𝛽(𝑗) the
job succeeding 𝑗 in 𝜎ℎ . Similarly, for each job 𝑗 ∈ 𝒥 𝑇 (𝑘) we denote with 𝛾(𝑗)
the job preceding 𝑗 in 𝜋𝑘 and with 𝛿(𝑗) the job succeeding 𝑗 in 𝜋𝑘 .
Let us now focus on the computation of a minimum makespan schedule of
a solution 𝐻. In order to compute 𝑆𝑗 and 𝐶𝑗 we assume that the preceding
jobs 𝛼(𝑗) and 𝛾(𝑗) (if exist) have already set 𝐶𝛼(𝑗) and 𝐶𝛾(𝑗) . We schedule
non-preemptive activities 𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) , 𝑔𝛼(𝑗)𝑗 and 𝑓𝛼(𝑗)𝑗 in the earliest available
time periods (see Figure 3.1). Then we schedule preemptive job 𝑗, possibly
splitting it in successive availability periods. Denoting with (⋅) and [⋅] open
and closed intervals respectively, the earliest available starting time for the
removal activity 𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) on machine ℎ′ is
∪
𝑋𝑗 = min{𝜏 : 𝜏 ≥ 𝐶𝛾(𝑗) , (𝜏, 𝜏 + 𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) ) ∩ [𝑟𝑖 , 𝑑˜𝑖 ] = ∅}.
𝑖∈𝒰 (ℎ′ )
Similarly, the earliest available starting times for the removal and setup activ-
ities 𝑓𝛼(𝑗)𝑗 and 𝑔𝛼(𝑗)𝑗 on machine ℎ are
∪
𝑌𝑗 = min{𝜏 : 𝜏 ≥ 𝐶𝛼(𝑗) , (𝜏, 𝜏 + 𝑔𝛼(𝑗)𝑗 ) ∩ [𝑟𝑖 , 𝑑˜𝑖 ] = ∅},
𝑖∈𝒰 (ℎ)
∪
𝑍𝑗 = min{𝜏 : 𝜏 ≥ 𝑋𝑗 +𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) , 𝜏 ≥ 𝑌𝑗 +𝑔𝛼(𝑗)𝑗 , (𝜏, 𝜏 +𝑓𝛼(𝑗)𝑗 )∩ [𝑟𝑖 , 𝑑˜𝑖 ] = ∅}.
𝑖∈𝒰 (ℎ)
Figure 3.1: Gantt chart for machines ℎ and ℎ′ and computation of 𝑆𝑗
If machine ℎ is unavailable at the release time 𝑟𝑗 of job 𝑗, let 𝑢(𝑗) be the last
unavailability on machine ℎ starting before 𝑟𝑗 , i.e., such that 𝑟𝑢(𝑗) = max{𝑟𝑙 ≤
𝑟𝑗 , 𝑙 ∈ 𝒰(ℎ)}. Then, job 𝑗 cannot start before 𝑅𝑗 = max{𝑑˜𝑢(𝑗) ; 𝑟𝑗 }. Therefore,

the earliest available starting time of 𝑗 is:
𝑆𝑗 = max{𝑅𝑗 ; 𝑍𝑗 + 𝑓𝛼(𝑗)𝑗 }. (3.1)
The earliest completion time of preemptive job 𝑗 equals 𝑆𝑗 + 𝑝𝑗 plus the

total time machine ℎ is unavailable for processing between the start and the
completion of job 𝑗. Let us denote with 𝑢1 , . . . 𝑢𝑣 the sequence of unavailabili-
ties in 𝒰(ℎ) starting after 𝑆𝑗 , ordered for increasing values of their release times
𝑆𝑗 ≤ 𝑟𝑢1 ≤ . . . ≤ 𝑟𝑢𝑣−1 ≤ 𝑟𝑢𝑣 , and let 𝑝𝑢1 , . . . 𝑝𝑢𝑣 be their respective processing
time. Also, let 𝑢𝑣(𝑗) be the last unavailability on machine ℎ before 𝐶𝑗 , i.e.,
∑𝑙
𝑣(𝑗) = min{𝑙 : 𝑆𝑗 + 𝑝𝑗 + 𝑖=1 𝑝𝑢𝑖 ≤ 𝑟𝑢𝑙+1 }. Then, the completion time of job
𝑗 is:
𝑣(𝑗)
∑
𝐶𝑗 = 𝑆𝑗 + 𝑝𝑗 + 𝑝𝑢𝑖 . (3.2)
𝑖=1
We denote the pair (𝑆, 𝐶) computed according to equation (3.1) and (3.2)
as the schedule associated to solution 𝐻. Let us define for job 𝑗 a modified
processing time 𝑝ˆ𝑗 = 𝐶𝑗 − 𝑆𝑗 and a modified release time 𝑟ˆ𝑗
{
𝑟𝑗 if 𝑆𝑗 = max{𝐶𝛼(𝑗) + 𝑔𝛼(𝑗)𝑗 ; 𝐶𝛾(𝑗) + 𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) } + 𝑓𝛼(𝑗)𝑗
𝑟ˆ𝑗 = (3.3)
𝑆𝑗 if 𝑆𝑗 > max{𝐶𝛼(𝑗) + 𝑔𝛼(𝑗)𝑗 ; 𝐶𝛾(𝑗) + 𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) } + 𝑓𝛼(𝑗)𝑗
A solution 𝐻 and the associated schedule can be represented with a graph

𝒢(𝐻) = (𝑉, 𝐸(𝜎) ∪ 𝐹 (𝜋) ∪ 𝐴). 𝑉 is the set of nodes, one for each job 𝑗 ∈ 𝒥 ,
weighted with 𝑝ˆ𝑗 , plus four auxiliary nodes 𝑠𝑡𝑎𝑟𝑡, 𝑒𝑛𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒.
𝐸(𝜎) is a set of arcs, one for each pair of consecutive nodes 𝑗 and 𝛽(𝑗) processed
on the same machine in 𝐻 and weighted with 𝑔𝑗𝛽(𝑗) + 𝑓𝑗𝛽(𝑗) . 𝐹 (𝜋) is a set of
arcs, one for each pair of consecutive nodes 𝑗 and 𝛿(𝑗) processed on the same
tool in 𝐻 and weighted with 𝑔𝑗𝛽(𝑗) +𝑓𝛼(𝛿(𝑗))𝛿(𝑗) . Finally, 𝐴 is a set of additional
arcs. For each node 𝑗 ∈ 𝒥 there is an arc in 𝐴 from 𝑠𝑡𝑎𝑟𝑡 to 𝑗, with weight 𝑟ˆ𝑗 ,
an arc (𝑗, 𝑒𝑛𝑑) ∈ 𝐴, with weight zero, an arc (𝑗, 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑) ∈ 𝐴 if a deadline
is defined for 𝑗, with weight −𝑑˜𝑗 , and an arc (𝑗, 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) ∈ 𝐴 if a due date is
defined for 𝑗, with weight −𝑑𝑗 .
Figure 3.2 shows the pictorial representation of a node 𝑗 and associated arcs
in 𝒢(𝐻), where arcs in 𝐸(𝜎)∪𝐴 are depicted with solid lines while arcs in 𝐹 (𝜋)
are depicted with dashed lines. Note that the graph structure depends on the
assignment and sequencing of the jobs on tools and machines, while the arc
weights also depend on the assignment of the unavailabilities to the machines.
Figure 3.2: Node 𝑗 and weighted sequencing arcs in 𝒢(𝐻)
For a given graph 𝒢, we define the head ℎ(𝑗) of node 𝑗 as the length of
the longest path in 𝒢 from 𝑠𝑡𝑎𝑟𝑡 to 𝑗 (excluding the weight of node 𝑗) and
the tail 𝑞𝑎 (𝑗) as the length of the longest path from 𝑗 to the auxiliary node
𝑎 ∈ {𝑒𝑛𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒} (including the weight of node 𝑗). With this
notation, the starting time 𝑆𝑗 of job 𝑗 in a solution is the head of the node
associated to job 𝑗. Then, ℎ(𝑒𝑛𝑑) and max{0, ℎ(𝑣𝑖𝑜𝑙 𝑑𝑢𝑒)} are equal to the
makespan 𝐶𝑚𝑎𝑥 and the maximum tardiness 𝑇𝑚𝑎𝑥 of the solution, respectively.
A solution 𝐻 is feasible if each job is assigned to a compatible machine and
to a compatible tool, each unavailability is assigned to a compatible machine,
unavailabilities assigned to the same machine are non-overlapping, and 𝒢(𝐻) =
(𝑉, 𝐸(𝜎) ∪ 𝐹 (𝜋) ∪ 𝐴) is acyclic. A schedule (𝑆, 𝐶) is feasible if the associated
solution 𝐻 is feasible and ℎ(𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑) ≤ 0, which implies ℎ(𝑖) + 𝑝ˆ𝑗 ≤ 𝑑˜𝑗 for
each 𝑗 ∈ 𝒥 .
3.4 Tabu search algorithm

In this section, we describe our tabu search algorithm. Section 3.4 describes
the algorithm used to find an initial solution, not necessarily feasible. Section
3.4 shows the basic moves used by the tabu search algorithm and structural
properties of the neighborhood based on these moves. In Section 3.4 we define
a restricted version of the neighborhood, which is used by our tabu search
algorithm. Finally, in Section 3.4, we describe two procedures to evaluate the
quality of a neighbor.
Greedy algorithm
A fast and simple greedy algorithm is used to obtain an initial solution. The al-
gorithm is designed to reproduce the behavior of human scheduler when build-
ing a feasible schedule. In fact, the human schedulers in the plant do not
follow any formal procedure to schedule production orders, and the schedules
are simply the result of intuition and past experience. However, the sched-
ules produced by hand are quite similar to those produced with the algorithm
summarized in the following steps:
1. compute an estimate workload for each machine as follows:

a) compute the minimum workload 𝑊ℎ for machine ℎ ∈ ℳ summing
up processing time + minimum setup time + minimum removal
time of all jobs that can be executed on machine ℎ only: 𝑊ℎ =
∑
𝑗:ℳ𝑗 ={ℎ} (𝑝𝑗 + min𝑖 {𝑓𝑖𝑗 } + min𝑖 {𝑔𝑖𝑗 }).
b) compute the quantity 𝑄(𝑖), equal to the processing time + mini-

mum setup time + minimum removal time of all jobs that can be
executed on machine ℎ and other i machines in ℳ, and add to 𝑊ℎ
the quantity 𝑄(𝑖)
𝑖+1 , for 𝑖 = 1, . . . , 𝑚 − 1.
2. assign human operators to machines, proportionally to the values 𝑊ℎ ;

3. partition the time horizon into 𝐿 time intervals of given length 𝜆, and
schedule the jobs in each time interval [(𝑙 − 1)𝜆, 𝑙𝜆], for 𝑙 = 1, . . . , 𝐿,
according to the following algorithm:
a) let 𝒥𝑙 be the set of jobs with deadline or due-date smaller than 𝑙𝜆;
b) group the jobs in 𝒥𝑙 requiring the same tool and sequence the jobs
in each group according to the ERD rule (Earliest Release Date first
rule);
c) sequence the groups one at a time by assigning a block to the next
available machine according the SST rule (Shortest Setup Time first
rule) until all groups are scheduled.
Neighborhood structure
Our tabu search algorithm makes use of two basic moves. The first one is
based on the interchange of a pair of adjacent jobs sequenced on the same ma-
chine/tool, which is commonly adopted in the tabu search literature on open
shop and job shop scheduling problems [36]. The second move is based on
removing a job from the sequence of jobs processed on a machine/tool and
inserting it in the sequence of another machine/tool. Similar moves are com-
monly used when dealing with parallel machine scheduling or vehicle routing
problems [9, 13].
The interchange move 𝜑𝑀 (𝑖, 𝑗) is defined as follows: given a solution 𝐻
and a pair of consecutive jobs 𝑖 and 𝑗 in 𝜎ℎ of machine ℎ, a new solution 𝐻 ′ is
obtained from 𝐻 reversing the precedence order (𝑖, 𝑗). A similar move 𝜑𝑇 (𝑖, 𝑗)
deals with rescheduling of consecutive jobs 𝑖 and 𝑗 in the sequence 𝜋𝑘 of tool
𝑘. When two jobs are processed consecutively both on the same machine ℎ
and tool 𝑘, then a move 𝜑𝑀 𝑇 (𝑖, 𝑗) is applied, which exchanges their relative
positions both in 𝜎ℎ and 𝜋𝑘 , in order to avoid a cycle of precedence constraints
between 𝑖 and 𝑗.
With the rerouting move 𝜃𝑀 (𝑖, 𝑗), 𝑖 can be either a job or an unavailability
while 𝑗 is a job. Moreover, 𝑖 and 𝑗 are processed on different machines ℎ and
ℎ′ , respectively, with ℎ′ ∈ ℳ𝑖 . If 𝑖 is a job, this move consists of removing
𝑖 from 𝜎ℎ and inserting it before 𝑗 in 𝜎ℎ′ . If 𝑖 is an unavailability, the move
consists of removing 𝑖 from machine ℎ and inserting it in the same machine of
𝑗 in its given time window. Similarly, move 𝜃𝑇 (𝑖, 𝑗) is applied to jobs 𝑖 and 𝑗
processed on different tools 𝑘 and 𝑘 ′ , respectively, with 𝑘 ′ ∈ 𝒯𝑖 .
Acyclicity property
A solution 𝐻 is feasible only if the corresponding graph 𝒢(𝐻) is acyclic. Our
tabu search algorithm does not perform moves leading to cyclic graphs. To
this aim, a cyclicity test is preliminarily checked before each move and the
move is removed from the neighborhood if it leads to a cycle. The test can be
performed in time 𝑂(𝑛) using the Bellman’s algorithm, but we next show that
this check can be performed in constant time if the conditions of Theorems
3.4.1 or 3.4.2 hold.
In the following we call critical path of 𝒢(𝐻) one of the longest paths from
𝑠𝑡𝑎𝑟𝑡 to one of the auxiliary nodes and denote 𝐻 the incumbent solution, 𝐻 ′
the solution obtained after a move, ℎ(𝑖) the head of node 𝑖 in 𝐻 and ℎ′ (𝑖) the
head of node 𝑖 in 𝐻 ′ .
Theorem 3.4.1 Given an arc (𝑖, 𝑗) on the critical path of 𝒢(𝐻), the inter-
change moves 𝜑𝑀 (𝑖, 𝑗), 𝜑𝑇 (𝑖, 𝑗), and 𝜑(𝑖, 𝑗)𝑀 𝑇 do not create cycles.
Proof. Let us suppose that there is a cycle in 𝒢(𝐻 ′ ) after a move 𝜑(𝑖, 𝑗).
Thus, there must be a path in 𝒢(𝐻) from 𝑖 to 𝑗, disjoint from arc (𝑖, 𝑗). Let
us consider the three moves separately.
∙ 𝜑𝑀 𝑇 (𝑖, 𝑗) move: in this case 𝑗 = 𝛽(𝑖) = 𝛿(𝑖) and there are no other arcs
outgoing from 𝑖, other than those ingoing in 𝑗 or in the auxiliary nodes.
Therefore, there is no path from 𝑖 to 𝑗, disjoint from arc (𝑖, 𝑗) in 𝒢(𝐻 ′ ),
a contradiction.
∙ 𝜑𝑀 (𝑖, 𝑗) move: in this case 𝑗 = 𝛽(𝑖). Let us suppose that a path 𝑝 from
𝑖 to 𝑗 exists in 𝒢(𝐻), besides arc (𝑖, 𝑗). This path must include at least
arcs (𝑖, 𝛿(𝑖)) and (𝛾(𝑗), 𝑗), which are the only arcs outgoing from 𝑖 and
ingoing in 𝑗 other than (𝑖, 𝑗) and the arcs of set 𝐴. There are only two
possibilities: either 𝑇𝑖 ∕= 𝑇𝑗 or 𝑇𝑖 = 𝑇𝑗 . In both cases, path 𝑝 includes at
least the removal of tool 𝑇𝑖 , the setup of tool 𝑇𝑗 and the processing time
𝑝𝛿(𝑖) > 0. If 𝑇𝑖 = 𝑇𝑗 the length of 𝑝 is strictly larger than the length of arc
(𝑖, 𝑗). If 𝑇𝑖 ∕= 𝑇𝑗 it follows from the triangular inequality that the weight
of all setups occurring in 𝑝 is larger or equal to 𝑔𝑖𝑗 + 𝑓𝑖𝑗 . Therefore, the
weight of 𝑝 is strictly larger than the weight of the critical arc (𝑖, 𝑗), a
contradiction.
∙ 𝜑𝑇 (𝑖, 𝑗) move: in this case 𝑗 = 𝛿(𝑖). Let us suppose that a path 𝑝 from
𝑖 to 𝑗 exists in 𝒢(𝐻), besides arc (𝑖, 𝑗). This path must include at least
arcs (𝑖, 𝛽(𝑖)) and (𝛼(𝑗), 𝑗), which are the only arcs outgoing from 𝑖 and
ingoing in 𝑗 other than (𝑖, 𝑗) and the arcs of set 𝐴. Also in this case, if
follows from the triangular inequality that the length of path 𝑝 is greater
than the weight of the critical arc (𝑖, 𝑗), a contradiction.
In conclusion, path 𝑝 cannot exist if the arc (𝑖, 𝑗) is critical, and the thesis
follows.
As far as the rerouting moves are concerned, let us first observe that there
can be a cycle in 𝒢(𝐻 ′ ) after move 𝜃𝑀 (𝑖, 𝑗) if and only if there is a path in
𝒢(𝐻) from 𝑗 to 𝛾(𝑖) or from 𝛿(𝑖) to 𝛼(𝑗). We notice that, if 𝑗 = 𝛽(𝑖) the
acyclicity of 𝒢(𝐻) implies that of 𝒢(𝐻 ′ ). Otherwise, a sufficient condition for
the acyclicity of 𝒢(𝐻 ′ ) is given by the following theorem. The proof directly
follows from results proved in [11].
Theorem 3.4.2 After a move 𝜃𝑀 (𝑖, 𝑗), if ℎ(𝑗) + 𝑝ˆ𝑗 > ℎ(𝛾(𝑖)) and ℎ(𝛿(𝑖)) +
𝑝ˆ𝛿(𝑖) > ℎ(𝛼(𝑗)) then 𝒢(𝐻 ′ ) is acyclic.
Similar conditions hold for 𝜃𝑇 (𝑖, 𝑗). When sufficient conditions do not hold the
algorithm explicitly checks the existence of a path from 𝑖 to 𝑗 on 𝒢(𝐻), besides
(𝑖, 𝑗). If such a path exists, the move is removed from the neighborhood.
Connectivity
In this section, we show that the neighborhood defined by moves 𝜑(𝑖, 𝑗) and
𝜃(𝑖, 𝑗) is connected, i.e., we prove that it is possible to reach a global minimum
starting from any feasible solution. Our proof is similar to that reported in [11].
Let 𝐴 be a resource assignment, i.e., the definition of sets 𝒥 𝑀 (ℎ), 𝒰(ℎ) and
𝒥 𝑇 (𝑘) for each machine ℎ ∈ ℳ and each tool 𝑘 ∈ 𝒯 . Let 𝐻𝐴 [respectively,
∗
𝐻𝐴 ] be a generic [an optimal] solution associated to 𝐴. 𝐻𝐴 [respectively,
∗
𝐻𝐴 ] defines the sequences [the optimal sequences] 𝜎ℎ and 𝜋𝑘 of elements in
𝒥 𝑀 (ℎ) and 𝒥 𝑇 (𝑘) for each ℎ ∈ ℳ and 𝑘 ∈ 𝒯 . We also call 𝒢(𝐻) the graph
representation of 𝐻 and 𝒢(𝐻) its transitive closure, i.e., the graph obtained
from 𝒢(𝐻) including all the redundant arcs. A first result is the following:
∗
Lemma 3.4.1 Given a resource assignment 𝐴, an optimal sequencing 𝐻𝐴 and
a solution 𝐻𝐴 , if 𝐻𝐴 is not optimal there is an arc (𝑖, 𝑗) such that (𝑖, 𝑗) is
∗
critical in 𝒢(𝐻𝐴 ) and such that (𝑗, 𝑖) ∈ 𝒢(𝐻 𝐴 ).
Proof. Let us suppose that all the critical arcs of 𝒢(𝐻𝐴 ) also belong to
∗ ∗
𝒢(𝐻 𝐴 ) as well. Therefore all the critical paths of 𝒢(𝐻𝐴 ) also belong to 𝒢(𝐻 𝐴 ),
∗
thus implying that 𝐻𝐴 is not optimal, a contradiction. Hence, there must be
∗
at least a critical arc (𝑖, 𝑗) ∈ 𝒢(𝐻𝐴 ) that does not belong to 𝒢(𝐻 𝐴 ), i.e., such
∗
that (𝑗, 𝑖) ∈ 𝒢(𝐻 𝐴 ).
From this lemma the following theorem can be proved.
Theorem 3.4.3 Given a resource assignment 𝐴 and a solution 𝐻𝐴 , if 𝐻𝐴 is

not optimal there is a sequence of interchange moves leading from 𝐻𝐴 to an
∗
optimal solution 𝐻𝐴 .
Proof. The proof directly follows from Lemma 3.4.1 and Theorem 3.4.1.
∗
Starting from 𝐻𝐴 and given an optimal solution 𝐻𝐴 , Lemma 3.4.1 guarantees
that there exists a pair of consecutive jobs that can be reversed, and Theorem
˜ 𝐴 , is feasible. If 𝐻
3.4.1 guarantees that the resulting solution, say 𝐻 ˜ 𝐴 is optimal
the thesis follows, otherwise the same procedure can be repeated starting from
𝐻˜ 𝐴 , finally leading to an optimal solution.
We have shown how an optimal sequencing for a given assignment 𝐴 can

be reached starting from any solution. We next show that an optimal assign-
ment can be reached starting form any assignment. To this aim, we prove the
following preliminary result.
Theorem 3.4.4 Given a solution 𝐻, a machine ℎ, a tool 𝑘 and a job 𝑖, com-

patible with machine ℎ [with tool 𝑘], if 𝑖 ∕∈ 𝒥 𝑀 (ℎ) [if 𝑖 ∕∈ 𝒥 𝑇 (𝑘)] there always
exists a rerouting move that moves 𝑖 to 𝒥 𝑀 (ℎ) [respectively, to 𝒥 𝑇 (𝑘)] leading
to a feasible solution.
Proof. Theorem 3.4.2 provides sufficient conditions for acyclicity after a rerout-
ing move. Therefore, to demonstrate the thesis, it is sufficient to show that,
if job 𝑖 is compatible with machine ℎ [with tool 𝑘], and given 𝜎ℎ [given 𝜋𝑘 ],
there are always in 𝜎ℎ [in 𝜋𝑘 ] two consecutive jobs 𝑙 and 𝑗 such that 𝑖 can be
inserted between 𝑙 and 𝑗.
We limit ourselves to prove this for move 𝜃𝑀 (𝑖, 𝑗) only, the proof for 𝜃𝑇 (𝑖, 𝑗)
being very similar. First observe that every arc in 𝜎ℎ always satisfies at least one
of the two conditions in theorem 3.4.2. In fact, if the first condition is not true,
then ℎ(𝑗) + 𝑝ˆ𝑗 ≤ ℎ(𝛾(𝑖)). It follows that ℎ(𝑙) < ℎ(𝑗) + 𝑝ˆ𝑗 ≤ ℎ(𝛾(𝑖)) < ℎ(𝛿(𝑖)) +
𝑝ˆ𝛿(𝑖) . Similarly, if the second condition is not true, then ℎ(𝛿(𝑖)) + 𝑝ˆ𝛿(𝑖) ≤ ℎ(𝑙),
which implies ℎ(𝑗) + 𝑝ˆ𝑗 ≥ ℎ(𝑙) + 𝑝ˆ𝑙 + 𝑝ˆ𝑗 > ℎ(𝑙) ≥ ℎ(𝛿(𝑖)) + 𝑝𝛿(𝑖) > ℎ(𝛾(𝑖)).
In particular the second condition is always satisfied for node 𝑠𝑡𝑎𝑟𝑡 and the
first for at least an auxiliary node 𝑖 ∈ {𝑒𝑛𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒}. Note also
that 𝑖 cannot satisfy the second condition. Then, in 𝜎ℎ there must be one last
node 𝑙 such that ℎ(𝛿(𝑖)) + 𝑝ˆ𝛿(𝑖) > ℎ(𝑙) and ℎ(𝛿(𝑖)) + 𝑝ˆ𝛿(𝑖) ≤ ℎ(𝛽(𝑙)). Therefore,
𝑗 = 𝛽(𝑙) must satisfy the condition ℎ(𝑗) + 𝑝ˆ𝑗 > ℎ(𝛾(𝑖)), which concludes the
proof.
Theorem 3.4.5 The neighborhood defined by moves 𝜑 and 𝜃 is connected.
Proof. Consider an optimal solution 𝐻 ∗ . Theorem 3.4.3 shows that starting

∗
from any solution 𝐻𝐴 it can be reached an optimal sequencing 𝐻𝐴 for the
∗
given assignment 𝐴. If 𝐻𝐴 is not globally optimal, there must be at least a
∗
job 𝑖 which is assigned to a different resource in 𝐻𝐴 and 𝐻 ∗ . Theorem 3.4.4
guarantees that there exists a rerouting move that moves 𝑖 to the same machine
as in 𝐻 ∗ , thus leading to a new feasible solution 𝐻 ′ . If 𝐻 ′ is optimal the thesis
follows, otherwise the same procedure can be repeated starting from 𝐻 ′ , finally
leading to an optimal solution.
Neighborhood exploration
At each step of the algorithm we restrict the interchange move to consecutive
jobs (𝑖 and 𝛼(𝑖) or 𝛾(𝑖)) on a critical path, i.e., a longest path from 𝑠𝑡𝑎𝑟𝑡 to
one of the other auxiliary nodes. This is a common strategy, e.g., when solving
job shop scheduling problems [36]. Specifically, we analyze a critical path from
𝑠𝑡𝑎𝑟𝑡 to 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑 when ℎ(𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑) > 0. Otherwise, we explore the paths
from 𝑠𝑡𝑎𝑟𝑡 to 𝑒𝑛𝑑 and 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒.
When dealing with the rerouting move 𝜃𝑀 (𝑖, 𝑗), we can move either jobs
or unavailabilities. In the former case, we restrict the choice of 𝑖 to the jobs
positioned on a critical path and 𝑗 to those nodes such that one of the two
following conditions is satisfied:
∙ there is a strictly positive slack time Δ𝑗 > 0 before 𝑗, on the machine

processing it, during which the machine is available and not busy;
∙ 𝑗 = 𝛿(𝑖), i.e., 𝑗 is the job using the same tool of 𝑖, immediately after it.
When the number of operators in a shift is smaller than 𝑏 times the number
of machines, we also allow to move unavailabilities. We say that an unavail-
ability 𝑢 is critical if one of the two following conditions holds: (1) there is a
node 𝑗 on a critical path of 𝒢(𝐻) and 𝑢 interrupts the processing of job 𝑗; (2)
𝑟ˆ𝑗 > 𝑟𝑗 and 𝑑˜𝑢 equals one of the quantities 𝑋𝑗 , 𝑌𝑗 , 𝑍𝑗 , 𝑅𝑗 defined in Figure 3.1.
We allow moving an unavailability 𝑖 with move 𝜃𝑀 (𝑖, 𝑗) only if 𝑖 is a critical
unavailability.
Critical paths and extended critical paths

We define two different critical paths. One is the classical longest path on
𝒢(𝐻) from 𝑠𝑡𝑎𝑟𝑡 to a specific auxiliary node, i.e., the path for which the sum
of the arc weights is maximum. This path might contain a small number of arcs
when its first arc is a modified release time 𝑟ˆ𝑗 > 𝑟𝑗 . In this case 𝑟ˆ𝑗 is computed
according to (3.3) and can take into account the sequencing of a large number
of jobs. Therefore, the starting time of job 𝑗 might be reduced as well by
anticipating the starting time of job 𝛼(𝑗), 𝛾(𝑗) or by rerouting one of these
two jobs since their modification can affect the value of 𝑟ˆ𝑗 . In other words,
incorporating in the critical path a longest path from 𝑠𝑡𝑎𝑟𝑡 to node 𝑗 different
from arc 𝑟ˆ𝑗 , would allow a larger possibility to improve upon the incumbent
solution. More formally, let us consider an ordinary longest path from 𝑠𝑡𝑎𝑟𝑡 to
any auxiliary node 𝑎 ∈ {𝑒𝑛𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒}, and let 𝑗 be the first node
after 𝑠𝑡𝑎𝑟𝑡 on this path. The extended critical path is recursively defined as
the path including all the nodes on the longest path plus the extended critical
path from 𝑠𝑡𝑎𝑟𝑡 to 𝑗. The latter quantity is the empty set if 𝑆𝑗 = 𝑅𝑗 holds in
equation (3.1). If 𝑆𝑗 > 𝑅𝑗 then, if 𝑌𝑗 + 𝑔𝛼(𝑗)𝑗 ≥ 𝑋𝑗 + 𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) the extended
critical path includes the longest path from 𝑠𝑡𝑎𝑟𝑡 to 𝛼(𝑗), otherwise it includes
the longest path from 𝑠𝑡𝑎𝑟𝑡 to 𝛾(𝑗). These paths are evaluated iteratively with
the same procedure.
Move evaluation
In the neighborhood of the incumbent solution 𝐻 we look for a solution 𝐻 ′
minimizing the following penalty function.
𝑓 (𝐻 ′ ) = 𝑏 ∗ 𝑚𝑎𝑥{0, ℎ(𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑)} + 𝑐 ∗ ℎ(𝑒𝑛𝑑) + 𝑑 ∗ 𝑚𝑎𝑥{0, ℎ(𝑣𝑖𝑜𝑙 𝑑𝑢𝑒)}. (3.4)
We developed two alternative algorithms for evaluating 𝑓 (𝐻 ′ ) after a move.
The first one gives an estimate of 𝑓 (𝐻 ′ ) in constant time, while the second
provides the exact value of 𝑓 (𝐻 ′ ) in linear time. At each step of the tabu
search, the neighbor with the smallest value of 𝑓 (𝐻 ′ ) is selected as the new
incumbent, and the schedule is updated accordingly. Then, according to the
equations (3.1) and (3.2) of Section 3.4, job starting and completion times are
updated in 𝒢(𝐻). We next describe the two evaluation algorithms.
Approximate evaluation
The approximate evaluation of 𝑓 (𝐻 ′ ) consists of using heads and tails of 𝒢(𝐻)
to estimate the length of a longest paths from 𝑠𝑡𝑎𝑟𝑡 to an auxiliary node 𝑒𝑛𝑑,
𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑, or 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒. We recall the notation ℎ(𝑖) and 𝑞𝑎 (𝑖) [respectively, ℎ′ (𝑖)
and 𝑞𝑎′ (𝑖)] to define the length of the longest path in 𝒢(𝐻) [respectively, in
𝒢(𝐻 ′ )] from node start to 𝑖 and from 𝑖 to node 𝑎 ∈ {𝑒𝑛𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒}.
With respect to move 𝜑(𝑖, 𝑗), the estimate 𝐿′𝑎 of the length of a longest path in
𝒢(𝐻 ′ ) from 𝑠𝑡𝑎𝑟𝑡 to auxiliary node 𝑎 is computed as an estimate of the longest
path passing through 𝑖 or 𝑗:
𝐿′𝑎 = 𝑚𝑎𝑥{ℎ′ (𝑖) + 𝑞𝑎′ (𝑖), ℎ′ (𝑗) + 𝑞𝑎′ (𝑗)}. (3.5)
𝑀
As for the solutions obtained with the 𝜑 (𝑖, 𝑗) move, we have (see Figure 3.3):
ℎ′ (𝑗) = max{𝑌𝑖 + 𝑔𝛼(𝑖)𝑗 + 𝑓𝛼(𝑖)𝑗 ; 𝑋𝑗 + 𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) + 𝑓𝛼(𝑖)𝑗 ; 𝑅𝑗 }
ℎ′ (𝑖) = max{ℎ′ (𝑗) + 𝑝𝑗 + 𝑔𝑗𝑖 + 𝑓𝑗𝑖 ; 𝑋𝑖 + 𝑔𝛾(𝑖)𝛽(𝛾(𝑖)) + 𝑓𝑗𝑖 ; 𝑅𝑖 }
𝑞𝑎′ (𝑖) = max{𝑝𝑖 + 𝑔𝑖𝛽(𝑗) + 𝑓𝑖𝛽(𝑗) + 𝑞𝑎 (𝛽(𝑗)); 𝑝𝑖 + 𝑔𝑖𝛽(𝑗) + 𝑓𝛼(𝛿(𝑖))𝛿(𝑖) + 𝑞𝑎 (𝛿(𝑖))}
𝑞𝑎′ (𝑗) = max{𝑝𝑗 + 𝑔𝑗𝑖 + 𝑓𝑗𝑖 + 𝑞𝑎′ (𝑖); 𝑝𝑗 + 𝑔𝑗𝑖 + 𝑓𝛼(𝛿(𝑗))𝛿(𝑗) + 𝑞𝑎 (𝛿(𝑗))}.
Figure 3.3: Approximate evaluation of move 𝜑𝑀 (𝑖, 𝑗).
These four quantities can be computed in constant time using the information
available from 𝒢(𝐻). For moves 𝜑𝑇 (𝑖, 𝑗), 𝜑𝑀 𝑇 (𝑖, 𝑗) there are similar equa-
tions. As for moves 𝜃𝑀 (𝑖, 𝑗) [respectively, 𝜃𝑇 (𝑖, 𝑗)] we estimate the length of
two longest paths: the one passing through the former nodes 𝛼(𝑖) and 𝛽(𝑖)
[respectively, 𝛾(𝑖) and 𝛿(𝑖)] and the one passing through 𝑖 in 𝒢(𝐻 ′ ). Also these
quantities can be computed in constant time using the information available
from 𝒢(𝐻).
Exact evaluation
We first notice that when changing the sequences 𝜎 and 𝜋, also the arc weights
in 𝒢(𝐻) may change. For this reason, it is necessary re-computing the exact
values for the starting/completion times of each job after each move. With
our exact evaluation strategy we compute these exact values not only after the
application of a move, but also for evaluating the neighborhood. We next show
that this computation requires linear time if the nodes of 𝒢(𝐻 ′ ) are numbered
according to a topological order.
Theorem 3.4.6 The exact evaluation of function 𝑓 (𝐻 ′ ) can be computed in

time 𝑂(𝑛 + 𝑞).
Proof. Let 𝑇 𝑂(𝑗) be the position of node 𝑗 in a topological order of the

nodes of 𝒢(𝐻 ′ ). We notice that, for both kinds of moves 𝜑(𝑖, 𝑗) and 𝜃(𝑖, 𝑗), the
starting times of the nodes preceding min{𝑇 𝑂(𝑖), 𝑇 𝑂(𝑗)} remain unchanged
when passing from 𝐻 to 𝐻 ′ . If we are moving an unavailability, updating
the values 𝑅𝑗 for all 𝑗 ∈ 𝒥 requires linear time if the unavailabilities and the
jobs are ordered for increasing values of 𝑟𝑗 . Then, we consider the jobs in
topological order. For each job 𝑗 to be processed on machine ℎ, we compute
its starting time 𝑆𝑗 by first scheduling the removal time 𝑔𝛼(𝑗)𝑗 on machine
ℎ. If the removal time can be accommodated between the completion of job
𝛼(𝑗) and the start of the next unavailability in 𝒰(ℎ) this position is accepted,
otherwise the value 𝑌𝑗 is computed by scanning the list of unavailabilities in
𝒰(ℎ). Similar computation is necessary to compute 𝑋𝑗 and to position the
removal time 𝑔𝛾(𝑗)𝛽(𝛾(𝑗)) on the machine processing job 𝛾(𝑗) and then the setup
time 𝑓𝛼(𝑗)𝑗 . Finally, 𝑆𝑗 can be computed as in equation (3.1). Given 𝑆𝑗 , the
completion time 𝐶𝑗 can be computed in linear time according to equation (3.2)
by computing the value 𝑣(𝑗) and inserting the unavailabilities in 𝒰(ℎ) one
at a time for increasing release time, starting from 𝑆𝑗 . Note that the whole
procedure requires a sequence of elementary steps, each requiring constant
time. At each elementary step either: (𝑖) a removal or a setup is positioned in
the schedule, or (𝑖𝑖) the starting/completion time of a job is defined, or (𝑖𝑖𝑖) it
is decided that some unavailability precedes one of the previous values. This
unavailability is not considered again in subsequent computations. Therefore,
the overall evaluation requires a total of 𝑂(𝑛 + 𝑞) elementary steps, and the
thesis follows.
3.5 Computational Experiments

In this section we describe the performance of four different versions of our tabu
search algorithm, developed by varying the size of the neighborhood and the
evaluation strategy. We evaluate either the classical critical path (option A) or
the extended one (option B) described in Section 3.4. We estimate the penalty
function 𝑓 (𝐻), for each 𝐻 in the neighborhood of the incumbent, by choosing
either the approximate evaluation (option C) or the exact one (option D), as
described in Section 3.4. We have, therefore, four versions of the algorithm for
the pairs of options A-C, A-D, B-C and B-D.
Each version depends on two parameters, namely the tabu list length 𝜆
and the number 𝜈 of non-improving moves examined before applying a restart
strategy. Our restart strategy consists of moving one unavailability from a
machine to another, randomly chosen. This kind of move strongly disrupt the
schedule since it generates an overload equal to the duration of one shift in one
machine and a big slack in the other. For each version of the algorithm, 𝜆 and
𝜈 are calibrated with the procedure CALIBRA, described in [1], for varying
𝜆 in the interval [5, 20], and 𝜈 in the interval [100, 1000]. CALIBRA uses the
Taguchi methodology [44] for fractional factorial experimental designs coupled
with a local search procedure to estimate the best values of all parameters. The
resulting pairs (𝜆, 𝜈) for each version of our tabu search algorithm are: (9,876)
for A-C, (16,876) for A-D, (7,876) for B-C and (18,876) for B-D version.
We fixed the values 𝑏 = 1010 , 𝑐 = 105 and 𝑑 = 1 in the objective function
𝑓 (𝐻) for all experiments. This corresponds to giving maximum priority to the
respect of deadlines and then considering makespan and tardiness in lexico-
graphical order, since a tardiness of two weeks is penalized less than increasing
the makespan by one minute. In Section 3.5 we compare the four versions of
our tabu search algorithm and draw several conclusions. All versions of the
algorithm were coded in C language and were run on a Pentium⃝ R
4, 3.0 GHz
with 1024 MB Ram. Two different sets of problem instances, described in
the following section, were generated: the first set comes from the industrial
practice and consists of 2 real instances and 24 realistic instances divided into
three groups of easy, medium and hard instances. Realistic instances represent
a wide range of possibilities that can arise in practice. For the real instances
we compare the actual performance attained at the plant when scheduling by
hand and by computer. For the realistic instances we compare the performance
of our algorithms with that of the greedy algorithm described in Section 3.4,
which was designed to perform similarly to the human schedulers of the plant.
The second set of instances is randomly generated, in order to evaluate the
performance of our algorithm in a more general context.
Data set description

The two real instances, correspond to the real production plan for several weeks
of production during September and October 2006. The first instance concerns
with 18 days of production during which 26 production orders are scheduled.
The second instance concerns with 16 days of production during which 19
production orders are scheduled. In both instances, there are no urgent orders
(i.e., no deadlines). All the jobs are available from the first day and the due
dates are fixed equal to the end of the last working day. Operators availability
in each week allows to activate three blister lines from Monday to Friday for
two consecutive shifts of 7 hours in each day, plus a short shift of three hours
in which two blisters can be activated from Tuesday to Friday only.

The second set of 24 realistic instances is divided into three groups with 8
instances in each group. The first group contains easy instances. There are no
urgent orders, the release dates [the due dates] coincide with the start of the
first week [the end of the second week] for all jobs and the total processing times
of all jobs (with the exclusion of removal and setup times) is approximately 50%
of the department capacity. The second group contains instances of medium
level of difficulty. There are no urgent orders but the release dates and the due
dates may vary over the two weeks and the workload is slightly larger. The
third group contains hard instances, with urgent orders, variable release/due
dates and larger workload. Instances of this kind may arise when a disruption
occurs in a different plant and its production is redirected to other plants, thus
causing a larger workload and a number of urgent orders.
The second data set consists of 120 random instances, obtained by generat-
ing 10 instances for each pair (𝑛, 𝑚), with the number of jobs 𝑛 varying in the
set {20, 40, 60, 100}, and the number 𝑚 of machines varying in {2, 3, 4}. Pro-
cessing times, release dates, due dates, deadlines, setups and removal times are
also randomly generated, as well as the tool assignment for each job. The total
workload for each instance is approximately equal to 90% of the department
capacity.
Computational results
In this section we report on our computational experience on the real, realistic
and random instances described in Section 3.5.
Real and realistic instances

In Table 3.1 we report on the results achieved by the four version of our tabu
search. In columns 2 and 3 the makespan (in hours) and the maximum tar-
diness (in hours) for the manual solutions are shown and in the subsequent
columns the same values are reported for the four configurations A-C, A-D, B-
C and B-D. The first two lines refer to the two real instances while the following
three lines of the table to the realistic instances (in each line, the average over
the 8 instances is reported). For the two real instances, the greedy algorithm
of Section 3.4 achieves in both instances 𝑇𝑚𝑎𝑥 = 0, While 𝐶𝑚𝑎𝑥 = 393.00 and
𝐶𝑚𝑎𝑥 = 443.00, respectively for the first and the second instance. These values
are quite similar to those obtained manually, so the greedy algorithm can be
used as a surrogate of the human schedulers. Therefore, column “Manual” of
Table 3.1 reports results obtained by the human schedulers of the plant for
the real instances (rows 1 and 2), and the computation time is the time actu-
ally taken by the operators to compute a solution by hand. For the realistic
instances (rows E, M and D, corresponding to easy, medium and difficult in-
stances, respectively) we don’t have results from human schedulers so we use
the greedy algorithm as a surrogate of their performance, and in column 𝑇 𝑖𝑚𝑒
we report the computation time of the greedy algorithm. In the following five
lines we report the average computation time required and the standard devi-
ation of the makespan 𝐶𝑚𝑎𝑥 for each group of instances and each algorithm.
Table 3.1: Comparison between manual and computerized schedules

Manual A-C A-D B-C B-D
Inst. 𝐶𝑚𝑎𝑥 𝑇𝑚𝑎𝑥 𝐶𝑚𝑎𝑥 𝑇𝑚𝑎𝑥 𝐶𝑚𝑎𝑥 𝑇𝑚𝑎𝑥 𝐶𝑚𝑎𝑥 𝑇𝑚𝑎𝑥 𝐶𝑚𝑎𝑥 𝑇𝑚𝑎𝑥
1 408.75 0 380 0 377 0 377 0 377 0
2 440.25 0 424.25 0 424 0 424 0 424 0
E 255.38 0 249.38 0 240.14 0 249.63 0 238.50 0
M 368.31 77.31 256.13 13.56 248.63 0 254.56 0 248.88 0
D 381.13 90.13 267.69 0 266.94 0 270.19 0 264.63 0
𝜎 𝑇 𝑖𝑚𝑒 𝜎 𝑇 𝑖𝑚𝑒 𝜎 𝑇 𝑖𝑚𝑒 𝜎 𝑇 𝑖𝑚𝑒 𝜎 𝑇 𝑖𝑚𝑒
1 – > 3600 – 4 – 3 – 13 – 1
2 – > 3600 – <1 – 1 – <1 – 1
E 5.12 <1 6.66 11.63 8.56 10.29 3.70 13.38 8.02 11.75
M 21.43 <1 7.85 11.25 7.62 14.38 10.15 16.63 11.21 16.00
D 17.97 <1 9.04 15.00 8.95 21.13 6.37 15.13 7.65 18.88
The four versions of the tabu search algorithm clearly outperform the man-
ual schedules, with respect to both makespan and tardiness. Specifically, for
what concern the makespan 𝐶𝑚𝑎𝑥 , the improvement achieved by the tabu
search with respect to the manual/greedy algorithm is always quite larger than
the standard deviation. For what concern 𝑇𝑚𝑎𝑥 , the greedy algorithm violates
the due dates in the 16 medium and hard instances, the tabu search version A-
C violates the due dates in only one medium instance, the other three versions
do never violate the due dates. For what concern the violation of the deadlines
(not reported in table), the greedy algorithm violates the deadlines in the eight
hard instances while the four versions of the tabu search do never violate the
deadlines.
Random Instances
The second set of instances consists of 120 random instances described in Sec-
tion 3.5. Table in Figure 3.4 shows the performance of the four configurations
of our tabu search algorithm. For each version of the algorithm, columns 𝐶𝑚𝑎𝑥
and 𝑇𝑚𝑎𝑥 report the average values of makespan and maximum tardiness, re-
spectively, on the 10 instances associated to each pair (𝑛, 𝑚). Column 𝜎 shows
the standard deviation of 𝐶𝑚𝑎𝑥 over the 10 instances.
Figure 3.4: Performance of the tabu search algorithm for varying 𝑛 and 𝑚
A few comments are in order. Computing the exact value of the objective
function (option D) for all neighbors provide much better results than using
an approximate evaluation (option C). In particular, combination B-D outper-
forms the others with respect to both makespan and maximum tardiness.
Using extended paths provides slightly better results than using the clas-
sical paths in combination with the exact evaluation. When using the ap-
proximate evaluation, better performance are provided by the classical path.
In other words, exact evaluation performs better with a larger neighborhood,
while approximate evaluation performs best with a smaller neighborhood, the
improvements being reached after several restart phases.
It is interesting analyzing the time needed by the algorithm to reach the best
solution found within one minute of computation time. With combinations A-
C and A-D the best solutions are found after 7.53 and 9.97 seconds on average,
respectively. With combinations B-C and B-D the best solutions are found after
6.83 and 10.03 seconds on average, respectively. We notice that despite the
larger number of solutions to explore in each iteration using the extended path
requires approximately the same computation time to find the best solution.
3.6 Conclusions
In this chapter, we studied a practical scheduling problem arising in the pack-
aging department of a pharmaceutical production plant. The problem is for-
mulated as a multi-purpose machine scheduling problem with additional con-
straints. A tabu search algorithm is able to find good solutions within short
computation time, compared to the solutions found by hand and by a greedy al-
gorithm. The makespan reduction is between 3.6% and 7.5% for easy instances
and increases to more than 30% for hard instances, which is a remarkable im-
provement in the productivity of the plant. More important, when analyzed
by the plant managers the solutions were considered feasible in practice. The
results achieved confirm that scheduling technology is mature to solve complex
real problems. To this aim, however, it is important to face the complexity of
practical scheduling problems by using detailed scheduling models.
Chapter 4
Coordination of production
scheduling and distribution in a
pharmaceutical plant
In many industrial settings production scheduling decisions are weakly coordi-

nated. The flow of information is often unidirectional and limited to the output
of one department which determines input data and constraints to be satisfied
by the subsequent department. In this chapter we report on a practical case
study showing that closer coordination provided by fast automated scheduling
tools can generate significant cost savings. We focus on coordination between
the packaging of final products and their distribution to wholesalers, i.e the
coordination between Packaging and Distribution department of a pharmaceu-
tical plant. The scheduling problem is analyzed in the previous chapter while
the distribution problem can be formulated as a vehicle routing problem with
soft time windows. The combined scheduling and delivery problem, with the
objective of minimization of total production and distribution costs, is consid-
ered and two resolution approaches are proposed, i.e. a decentralized and a
centralized approach. As well as for the scheduling problem, we adapt a classic
tabu search algorithms for the resolution of both the distribution problem in the
decentralized approach and the combined problem in the centralized approach.
Computational experiments show that good solutions to difficult instances of
the combined problem can be obtained within less than a minute of computa-
tion with both approaches. The overall performance of the centralized approach
significantly improves that of the decentralized approach.
47
CHAPTER 4. COORDINATION OF PRODUCTION SCHEDULING AND
DISTRIBUTION IN A PHARMACEUTICAL PLANT 48
4.1 Introduction
In the last decades there is an increasing research activity on coordination of
multiple decisions in supply chain management as well as among different stages
of a production system. The need for coordination arise from the observation
that decisions made in a stage of the supply chain influence decisions made in
the other stages. Moreover, decisions that are locally the most convenient for
a particular stage can force the other stages to choose from a set of decisions
not very convenient for them. Coordinated decisions avoid the generation of
inconvenient constraints from a stage versus the following one, and allow the
following stage to choose from a better set of decisions than in an uncoordi-
nated scenario. In other words, coordination enables to take decisions that are
globally more convenient for the whole system.
Coordination issues are particularly important in the pharmaceutical supply
chain, in which the legal and economical implications of product stockout re-
quires the adoption of standards of product quality and availability close to
100%. Availability of final products requires not only to achieve excellence at
each stage of the planning process, from strategic planning to real time schedul-
ing and delivery, but also in the coordination between different stages.
The lack of coordination in a supply chain is mainly due to the variety of ac-
tors with conflicting objectives that compete and cooperate within the supply
chain. Nevertheless, even within the same company decisions can be scarcely
coordinated for several reasons, e.g., because they are taken by different de-
cision makers at different time points of the process and by considering only
a subset of all the constraints and factors affecting the overall company costs.
This is the case, for example, of production planning and scheduling. Schedul-
ing in a single department strongly depends on the production plan as well
as on scheduling in other departments. Unfortunately, production planning
and scheduling, as well as single departments, are usually loosely integrated.
Usually, the presence of large stocks between two adjacent departments com-
pensate for the lack of coordination between them; anyway, some benefits, as
the reduction of stocking costs, could be obtained by introducing a stronger
coordination. The need of coordination is more evident in departments that
operates as pull systems, i.e. systems where the operations in a stage are
guided by a request of subsequent stages. This is the case of the packaging and
distribution levels. This stages are guided by wholesalers orders that can dy-
namically vary. The two stages may have different response to these variation,
then, the decisions taken in the packaging stage result in constraints for the
distribution phase that may cause bad solutions. In such cases, coordination
may produce significant savings because the overall objective of both stages is
to reduce the overall company costs.
In this chapter we address a combined production scheduling and distri-

bution problem arising in a pharmaceutical production plant. We refer in
particular to the coordination between the packaging and the distribution of
finished products. The packaging stage is the last manufacturing stage of the
production process. Scheduling decisions are taken on a weekly basis indepen-
dently from the subsequent distribution stage. However, the decisions taken
result in constraints for the distribution department that might cause delays
or extra costs in the delivery of some products. Therefore, closer coordination
between the two departments might significantly improve the overall company
performance.
The production scheduling problem is described in details in Chapter 3,
while the distribution problem is a version of the vehicle routing problem with
soft time windows that takes into account multiple deliveries to the same cus-
tomer in the same or in different shipments. The overall objective function is
the minimization of total production and distribution costs. The purpose of
this study is to quantify the benefits of coordination for this difficult practical
case study.
Two different resolution approaches are presented: a decentralized ap-
proach, in which the production scheduling problem is solved independently
from the vehicle routing problem, and a centralized approach, in which the
two subproblems are solved simultaneously. The performance of the two ap-
proaches are then compared in order to evaluate the benefits of replacing the
currently used decentralized approach with centralized optimization.
The remainder of this chapter is structured as follows. After a brief intro-

duction in Section 4.1, in Section 4.2 we present a review of literature on supply
chain coordination and scheduling. In Section 4.3 we define the distribution
problem and a Tabu Search algorithm to solve it. Section 4.4 introduces the
combined problem and the two different resolution approaches: decentralized
and centralized. The computational experiments follow in Section 4.5.
4.2 Scheduling and delivery in literature

The coordination between different stages at the operational level is still an
under-researched topic in the academic literature, but is critical to the success-
ful implementation of planning activities, in particular for the pharmaceutical

industry. An integrated approach to planning and scheduling in the phar-
maceutical industry can be found in [50], where a hierarchically structured
moving horizon framework is proposed. The problem of integrating the pro-
duction schedules of two departments in the production process of a furniture
manufacturer has been studied by Agnetis et al [2]. The two departments rank
the jobs on the basis of their color and size respectively, but a common job
sequence that trades off the two departments’ objectives is needed.
The literature on integrated production scheduling and delivery is analyzed
by several authors. In the survey of Sarmiento and Nagi [47] various cases are
analyzed in which two or more different functions (supply process, distribu-
tion, inventory management, production scheduling . . . ), are integrated into
a single optimization model. In particular, papers on scheduling-inventory-
distribution integration are classified into different categories (single/multiple
supply location, deterministic and stochastic, routing and no-routing models).
The benefit of an integrated approach is demonstrated in many cases. Supply
chain scheduling is discussed in [21]. An arborescent supply chain is considered
with a supplier making deliveries to several manufacturers that, in turn, serve
several customers. Each actor is considered as a single machine and jobs are
delivered in batches. Also in this case, cooperation results in significant total
cost reduction. Routing decisions are considered in [8] where different cases of
scheduling and distributions are examined, with the aim to both maximize a
function of customer service level and to minimize a function of total delivery
costs. Two different machine configurations, single and parallel, and two situ-
ations for customers, single or multiple, are considered. Problems are divided
into two classes corresponding to two different measures of customer service
level: average delivery time in the first class and maximum delivery time in
the second one. Exact algorithms are provided for the easiest problems, while
intractability proofs and heuristic algorithms are proposed for more difficult
problems. Mak and Wong [27] presents a genetic algorithm to solve a complex
integrated inventory-production-distribution problem.
Tardiness or lateness issues are the main goals in the literature on news-
papers distribution [24, 46]. Hurter and Van Buer [24] study a problem of
coordination between the printing (i.e., production) and distribution depart-
ments in a newspaper company. The authors study the tradeoff between the
conflicting preferences of the two departments. Russell et al. [46] presents a
tabu search metaheuristic for the coordination of the production and delivery of
newspapers. The integrated approach significantly improves the performance
with respect to existing operations.
4.3 The distribution problem

The distribution problem 𝑉 𝑅𝑃 can be modeled as a Vehicle Routing Prob-
lem with soft Time Windows and Multiple Deliveries. A set of 𝑛 jobs 𝒥 =
{1, 2, ..., 𝑛}, each corresponding to a single production order, must be delivered
to a set of 𝑐 customers 𝒞 = {1, 2, ..., 𝑐}, from a single depot referred to as the
customer 0. A release time 𝑒𝑗 and a due date 𝑑𝑗 are associated to job 𝑗 ∈ 𝒥 .
Each job must be delivered by a single vehicle to a single customer. We denote
with 𝐶𝑗 ∈ 𝒞 the customer of job 𝑗. Differently from the most common defini-
tions of time windows for the vehicle routing problem, in our case the release
time of a job if related to the completion of its packaging operation while the
due date is related to its delivery date. Therefore, the vehicle carrying job 𝑗
cannot depart from the depot before 𝑒𝑗 . The tardiness of job 𝑗 delivered at
time 𝑡 to 𝐶𝑗 is max{0, 𝑡 − 𝑑𝑗 }. For some jobs a strict deadline can be specified
when a late delivery would cause a stockout at the final customer. We denote
as 𝑑˜𝑗 the deadline of job 𝑗 when specified. To each pair of customers (ℎ, 𝑘) is
associated a travel time 𝑡ℎ𝑘 . A set of 𝑟 vehicles 𝒱 = {1, 2, ..., 𝑟}, with 𝑟 ≥ 𝑛,
each with maximum capacity 𝑄 is available to deliver jobs to customers. In
our model, all jobs have the same size and therefore 𝑄 is the maximum number
of jobs that can be carried by a vehicle.
Finding a solution to 𝑉 𝑅𝑃 consists of solving the following two subprob-
lems:
(𝑖) Assign each job 𝑗 ∈ 𝒥 to a vehicle 𝑣 ∈ 𝒱. Let 𝒥 𝑉 (𝑣) be the set of

jobs assigned to vehicle 𝑣 and 𝒞 𝑉 (𝑣) = {𝐶𝑗 , 𝑗 ∈ 𝒥 𝑉 (𝑣)} be the set of
customers served by vehicle 𝑣.
(𝑖𝑖) Sequence the customers in 𝒞 𝑉 (𝑣) ∪ {0},𝑣 = 1, . . . , 𝑟. Let us denote with
𝜌𝑣 = (𝜌𝑣 (1), . . . , 𝜌𝑣 (∣𝒞 𝑉 (𝑣)∣)) the sequence of customers assigned to ve-
hicle 𝑣, and with 𝜌 the 𝑟-tuple (𝜌1 , 𝜌2 , . . . , 𝜌𝑟 ), i.e., the sequencing for all
vehicles. The route of vehicle 𝑣 always starts from the depot 0, visits the
customers in 𝜌𝑣 in the given sequencing and returns to the depot after
visiting the last customer in 𝜌𝑣 . Let 𝒥 𝑉 (𝑣, ℎ) = {𝑗 ∈ 𝒥 𝑉 (𝑣)∣𝐶𝑗 = ℎ} be
the set of jobs ordered by customer ℎ that are delivered by vehicle 𝑣.
A solution 𝜌 is feasible if: (𝑖) each job is assigned to a vehicle, (𝑖𝑖) each
vehicle delivers at most 𝑄 jobs, and (𝑖𝑖𝑖) each vehicle does not depart from the
depot before the maximum release date of the jobs to deliver, i.e., there is a
release time 𝐸𝑣 = max{𝑒𝑗 : 𝑗 ∈ 𝒥 𝑉 (𝑣)} for vehicle 𝑣.
Given a solution 𝜌 it is possible to calculate:
∙ the arrival time 𝐴𝑣ℎ of vehicle 𝑣 at customer ℎ. Letting 𝑖ℎ be the po-

sition of customer ℎ in sequence 𝜌𝑣 , i.e., ℎ = 𝜌𝑣 (𝑖ℎ ), we have: 𝐴𝑣ℎ =
𝐴𝑣𝜌𝑣 (𝑖ℎ −1) + 𝑡𝜌𝑣 (𝑖ℎ −1)ℎ , with 𝐴𝑣𝜌𝑣 (1) = 𝐸𝑣 + 𝑡0𝜌𝑣 (1) ;
∙ the arrival time 𝐴𝑗 of job 𝑗: 𝐴𝑗 = 𝐴𝜌𝑣 (𝐶𝑗 )𝐶𝑗 ;
∙ the total delivery time 𝑡(𝜌𝑣 ) of route 𝜌𝑣 of vehicle 𝑣 as the sum of all
travel times on the route.
A solution 𝜌 of the distribution problem can be represented with a graph
(see Figure 4.1) similar to the graph used to represent a solution 𝐻 of the
scheduling problem. It can be defined by 𝒢(𝜌) = (𝑉, 𝐸(𝜌) ∪ 𝐹 ), where 𝑉 is
a set of nodes, one for each job 𝑗 ∈ 𝒥 , for each customer ℎ ∈ 𝒞 𝑉 (𝑣), and
for each vehicle 𝑣 ∈ 𝒱, plus three auxiliary nodes 𝑠𝑡𝑎𝑟𝑡 𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒.
Hereinafter, unless specified otherwise, we will identify a node with the corre-
sponding vehicle, customer or job and vice versa. 𝐸(𝜌) is a set of arcs depending
on the chosen routing 𝜌. There is an arc in 𝐸(𝜌) connecting each node 𝑣 ∈ 𝑉
to the first node in the route 𝜌𝑣 , plus an arc between each pair of consecutive
nodes ℎ and 𝑘 in route 𝜌𝑣 for all 𝑣, weighted with 𝑡ℎ𝑘 , and an arc from each
node ℎ ∈ 𝒞 𝑉 (𝑣) to each node 𝑗 ∈ 𝒥 𝑉 (𝑣, ℎ). In the set of fixed arcs 𝐹 , there is
an arc from 𝑠𝑡𝑎𝑟𝑡 𝑑 to each node 𝑣 ∈ 𝒱, with weight 𝐸𝑣 , and from each node
𝑗 ∈ 𝒥 to 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑 if a deadline is defined for 𝑗, with weight −𝑑˜𝑗 , or from 𝑗 to
𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 if a due date is defined for 𝑗, with weight −𝑑𝑗 .
In 𝒢(𝜌) we define the head ℎ(𝑗) of a node 𝑗 as the length of longest path
from 𝑠𝑡𝑎𝑟𝑡 𝑑 to 𝑗 and its tail 𝑞𝑎 (𝑗) as the length of critical path from 𝑗 to an
auxiliary node 𝑎 ∈ {𝑣𝑖𝑜𝑙 𝑑𝑢𝑒, 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑}.
A Tabu search algorithm for the vehicle routing problem

Neighborhood definition
Our tabu search procedure for problem 𝑉 𝑅𝑃 implements the main features of
the TABUROUTE algorithm introduced by Gendrau, Hertz and Laporte [14],
adapted to our problem.
Two basic moves are used for generating the neighborhood. With the first
move (reroutingC ), all the jobs to be delivered by a vehicle to the same customer
are moved to the route of another vehicle. With the second move (reroutingJ ),
a single job is moved from a vehicle to another.
The reroutingC move 𝜓 𝐶 (ℎ, 𝑤) is defined as follows: given a solution 𝜌, a
customers ℎ in 𝜌𝑣 and a vehicle 𝑤 ∕= 𝑣, a new solution 𝜌′ is obtained from
Figure 4.1: Graph model for the distribution problem
𝜌 by moving customer ℎ and all the associated jobs to route 𝜌𝑤 , positioning

customer ℎ just before the closest customer 𝑘 = 𝑎𝑟𝑔𝑚𝑖𝑛𝑙∈𝒞 𝑉 (𝑤) {𝑡ℎ𝑙 } in 𝜌𝑤 . If
ℎ = 𝑘 (i.e., 𝑡ℎ𝑘 = 0), only the jobs are moved to 𝜌𝑤 and associated to 𝑘, while
customer ℎ is deleted from 𝜌𝑣 and not added to 𝜌𝑤 .
The reroutingJ move 𝜓 𝐽 (𝑗, 𝑤) consists in moving a single job 𝑗 from its
current vehicle, say 𝑣, to vehicle 𝑤 ∕= 𝑣. If 𝜌𝑤 already contains a customer
𝑘 = 𝐶𝑗 , then 𝑗 is added to 𝒥 𝑉 (𝑣, 𝑘), otherwise customer 𝐶𝑗 is added to 𝜌𝑤
and inserted in the route immediately before its closest customer 𝑘 in 𝜌𝑤 , i.e.,
the one with smallest 𝑡𝐶𝑗 𝑘 . If ∣𝒥 𝑉 (𝑣, 𝐶𝑗 )∣ = 1, move 𝜓 𝐽 (𝑗, 𝑤) coincides with
𝜓 𝐶 (𝐶𝑗 , 𝑤) and customer 𝐶𝑗 is removed from 𝜌𝑣 .
Other two moves are defined to be used as perturbation strategy. The unify
move joins two routes 𝜌𝑣 and 𝜌𝑤 in a single route, thus reducing the number
of vehicle used by the solution. The divide move generates two routes from
a route 𝜌𝑣 and adds a vehicle to the solution for the new route. The former
move is applied after a given number of iterations during which the algorithm
did not find feasible solutions, i.e., all the solutions explored violate the vehicle
capacity constraints. The latter perturbation move is applied after a given
number of iterations during which the algorithm was not able to improve the
current optimum.
Neighborhood exploration
Two strategies are used for neighborhood exploration. The first is based on the
critical path criteria, while the second randomly explores a subset of neighbors.
With the first strategy, the exploration is restricted to moves involving
nodes on a critical path, i.e., a longest path from 𝑠𝑡𝑎𝑟𝑡 𝑑 to node 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 or
𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑. Specifically, we consider a critical path from 𝑠𝑡𝑎𝑟𝑡 𝑑 to 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑 if
ℎ(𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑) > 0, otherwise a critical path from 𝑠𝑡𝑎𝑟𝑡 𝑑 to 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 if ℎ(𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) >
0. Let us denote with 𝒫ℎ the set of the 𝑝 customers closest to ℎ in terms of
time 𝑡ℎ𝑘 . Move 𝜓 𝐶 (ℎ, 𝑤) generates a neighbor for each customer ℎ served by
vehicle 𝑣 in the current critical path and for each vehicle 𝑤 ∕= 𝑣 such that:
∙ 𝑤 already serves customer ℎ;

∙ 𝑤 serves one customer 𝑘 belonging to 𝒫ℎ but not customer ℎ (in this case
ℎ is inserted before customer 𝑘);
∙ 𝑤 is empty.
Similarly, other neighbors are generated by moving only the last job 𝑗 on
the current critical path. Let 𝑣 be the vehicle delivering job 𝑗 and ℎ = 𝐶𝑗 ,
then the neighbor is generated by move 𝜓 𝐽 (𝑗, 𝑤), with 𝑤 chosen according to
the three previous conditions.
The random exploration is derived from the TABUROUTE algorithm but
with the following modifications to take into account the different objective
function of the problem. Let us partition the customer-set of 𝒢(𝜌) into three
sub-sets 𝑊 1 ,𝑊 2 and 𝑊 3 defined as follows. For each vehicle 𝑣, let us consider
its route 𝜌𝑣 and the associated delivery time ℎ(𝑘) for customer 𝑘 ∈ 𝒞 𝑉 (𝑣).
Let ℎ1 be the position of the last customer on 𝜌𝑣 for which the delivery time
violates the customer deadline, the value ℎ1 = 0 corresponding to the case in
which no deadline is violated:
ℎ1 = max{𝑖 : (𝑖 = 0)
∨ ( (1 ≤ 𝑖 ≤ ∣𝒞 𝑉 (𝑣)∣)
∧ (max𝑗∈𝒥 𝑉 (𝑣,𝜌(𝑖)) {ℎ(𝑗) + 𝑞𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑 (𝑗)} > 0) ) }
Let ℎ2 be the position of the last customer on 𝜌𝑣 after ℎ1 for which the
delivery time violates the customer due date, with ℎ2 = ℎ1 if no customer after
ℎ1 violates the due date:
ℎ2 = max{𝑖 : (𝑖 = ℎ1 )
∨ ( (ℎ1 + 1 ≤ 𝑖 ≤ ∣𝒞 𝑉 (𝑣)∣)
∧ (max𝑗∈𝒥 𝑉 (𝑣,𝜌(𝑖)) {ℎ(𝑗) + 𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝑗)} > 0) ) }
The set 𝑊 1 = {𝜌𝑣 (1), . . . , 𝜌𝑣 (ℎ1 )} contains all the customers from the be-
ginning of 𝜌𝑣 until ℎ1 , the set 𝑊 2 = {𝜌𝑣 (ℎ1 + 1), . . . , 𝜌𝑣 (ℎ2 )} contains all the
customers after ℎ1 until ℎ2 , and 𝑊 3 = {𝜌𝑣 (ℎ2 + 1), . . . , 𝜌𝑣 (∣𝒞 𝑉 (𝑣)∣)} contains
the remaining customers.
With the random exploration strategy, a set 𝒬 of 𝑞 customers is generated
by randomly choosing 𝜉 1 customers in 𝑊 1 , 𝜉 2 customers in 𝑊 2 and 𝜉 3 cus-
tomers in 𝑊 3 , where 𝜉 1 > 𝜉 2 > 𝜉 3 are three parameters of the algorithm such
that 𝑞 = 𝜉 1 + 𝜉 2 + 𝜉 3 . Then, for each customer ℎ ∈ 𝒬, neighbors are generated
by move 𝜓 𝐶 (ℎ, 𝑤), with 𝑤 chosen as in conditions above.
Move evaluation
Let 𝑇˜𝑚𝑎𝑥 = max{0, ℎ(𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑)} denote the maximum deadline violation,
𝑇𝑚𝑎𝑥 = max{0, ℎ(𝑣𝑖𝑜𝑙 𝑑𝑢𝑒)} the maximum tardiness, 𝑛𝑉 the number of vehi-
cles serving at least one customer and 𝑡𝑡𝑜𝑡 the total delivery time of all routes
of a solution 𝜌. The objective function of 𝑉 𝑅𝑃 is a weighed sum of 𝑇˜𝑚𝑎𝑥 ,
𝑇𝑚𝑎𝑥 , 𝑛𝑉 and 𝑡𝑡𝑜𝑡 :
𝑓𝑉 𝑅 (𝜌) = 𝜔 𝑇˜𝑚𝑎𝑥 + 𝜔1 𝑇𝑚𝑎𝑥 + 𝜔3 𝑛𝑉 + 𝜔4 𝑡𝑡𝑜𝑡 (4.1)

In our tabu search, the exploration of infeasible solutions is allowed in order
to search for more
∑ effective solutions, however infeasible solutions are penalized.
Letting 𝑠𝑡𝑜𝑡 = 𝑣∈𝒱 max{0, ∣𝒥 𝑉 (𝑣)∣ − 𝑄} be the total surplus of all vehicles,
the function used to evaluate the neighborhood of the incumbent solution 𝜌 is
the following:
𝑓2 (𝜌) = 𝑓𝑉 𝑅 (𝜌) + 𝜔5 𝑠𝑡𝑜𝑡 (4.2)
In the following we denote with 𝜌′ a generic solution in the neighborhood
of 𝜌 and with similar notation we denote the variables related to 𝜌′ . In or-
der to evaluate 𝜌′ , values 𝑛′𝑉 , 𝑠′𝑡𝑜𝑡 and 𝑡′𝑡𝑜𝑡 are calculated exactly for each
neighbor. In particular value 𝑛′𝑉 decreases when the only customer in a ve-
hicle is moved, and it increases when a customer is moved to an empty ve-
hicle. The new surplus 𝑠′𝑡𝑜𝑡 when a customer ℎ is moved from vehicle 𝑣 to
vehicle 𝑤 is calculated as 𝑠′𝑡𝑜𝑡 = 𝑠𝑡𝑜𝑡 + max{0, ∣𝒥 𝑉 (𝑣)∣ − 𝑄 − ∣𝒥 𝑉 (𝑣, ℎ)∣} −
max{0, ∣𝒥 𝑉 (𝑣)∣−𝑄}+max{0, ∣𝒥 𝑉 (𝑤)∣−𝑄+∣𝒥 𝑉 (𝑣, ℎ)∣}−max{0, ∣𝒥 𝑉 (𝑤)∣−𝑄},
in which max{0, ∣𝒥 𝑉 (𝑣)∣ − 𝑄 − ∣𝒥 𝑉 (𝑣, ℎ)∣} − max{0, ∣𝒥 𝑉 (𝑣)∣ − 𝑄} is the varia-

tion of surplus in the source vehicle 𝑣 and max{0, ∣𝒥 𝑉 (𝑤)∣ − 𝑄 + ∣𝒥 𝑉 (𝑣, ℎ)∣} −
max{0, ∣𝒥 𝑉 (𝑤)∣ − 𝑄} is the variation in the destination vehicle 𝑤. Simi-
larly, the new total delivery time 𝑡′𝑡𝑜𝑡 , when a customer ℎ is moved from ve-
hicle 𝑣 and inserted before customer 𝑘 in vehicle 𝑤, is calculated as 𝑡′𝑡𝑜𝑡 =
𝑡𝑡𝑜𝑡 + 𝑡𝜌𝑣 (𝑖ℎ −1)𝜌𝑣 (𝑖ℎ +1) − 𝑡𝜌𝑣 (𝑖ℎ −1)ℎ − 𝑡ℎ𝜌𝑣 (𝑖ℎ +1) + 𝑡ℎ𝑘 + 𝑡𝜌𝑤 (𝑖𝑘 −1)ℎ − 𝑡𝜌𝑤 (𝑖𝑘 −1)𝑘 ,
where 𝑡𝜌𝑣 (𝑖ℎ −1)𝜌𝑣 (𝑖ℎ +1) − 𝑡𝜌𝑣 (𝑖ℎ −1)ℎ − 𝑡ℎ𝜌𝑣 (𝑖ℎ +1) is the delivery time variation for
the source route and 𝑡ℎ𝑘 + 𝑡𝜌𝑤 (𝑖𝑘 −1)ℎ − 𝑡𝜌𝑤 (𝑖𝑘 −1)𝑘 that of the destination route.
In order to estimate the heads of nodes ℎ′ (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) and ℎ′ (𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑) we
use the following criteria. Let us first observe that moving jobs from 𝑣1 to 𝑣2
may cause a variation of the release time of the two vehicles. We denote with
Δ𝐸1 = 𝐸𝑣′ 1 − 𝐸𝑣1 and Δ𝐸2 = 𝐸𝑣′ 2 − 𝐸𝑣2 the variation of release time of vehicles
𝑣1 and 𝑣2 , respectively, when passing from 𝒢(𝜌) to 𝒢(𝜌′ ).
For a reroutingC move 𝜓 𝐶 (ℎ, 𝑣2 ), moving customer ℎ from vehicle 𝑣1 to
vehicle 𝑣2 before customer 𝑘 ∕= ℎ, we have 𝐸𝑣′ 2 = max{𝑒𝑗 : 𝑗 ∈ 𝒥 𝑉 (𝑣1 ) −
𝒥 𝑉 (𝑣1 , ℎ)} and 𝐸𝑣′ 1 = max{𝑒𝑗 : 𝑗 ∈ 𝒥 𝑉 (𝑣2 ) ∪ 𝒥 𝑉 (𝑣1 , ℎ)}. Then, we estimate
the new head ℎ′ (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) as the maximum of two quantities ℎ′1 (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) and
ℎ′2 (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) that take into account the contributions to ℎ′ (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) of vehicles
𝑣1 and 𝑣2 . Let us denote with 𝑇𝑘 = max{0, ℎ(𝑘) + max𝑗∈𝒥 𝑉 (𝑣,𝑘) {𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝑗)}}
the maximum tardiness of the jobs belonging to customer 𝑘 and delivered
by vehicle 𝑣. Then, the quantity ℎ′1 (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) is estimated as the maximum
between the tardiness associated to the customer preceding ℎ in 𝜌𝑣1 and the
tardiness of all customers following ℎ in 𝜌𝑣1 . Specifically, the new head of the
node preceding ℎ is ℎ′ (𝜌𝑣1 (𝑖ℎ − 1)) = ℎ(𝜌𝑣1 (𝑖ℎ − 1)) + Δ𝐸1 and its tardiness
is 𝑇𝜌′ 𝑣 (𝑖ℎ −1) = max{0, ℎ′ (𝜌𝑣1 (𝑖ℎ − 1)) + max𝑗∈𝒥 𝑉 (𝑣1 ,𝜌𝑣1 (𝑖ℎ −1)) {𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝑗)}}.
1
The new head of the node following ℎ is ℎ′ (𝜌𝑣1 (𝑖ℎ + 1)) = ℎ′ (𝜌𝑣1 (𝑖ℎ − 1)) +
𝑡𝜌𝑣1 (𝑖ℎ −1)𝜌𝑣1 (𝑖ℎ +1) while the tail of 𝜌𝑣1 (𝑖ℎ + 1) is unchanged and takes into
account also all the customers in 𝜌𝑣1 visited after 𝜌𝑣1 (𝑖ℎ + 1). The estimate of
ℎ′1 (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) is therefore:
ℎ′1 (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) = max{𝑇𝜌′ 𝑣 ′

(𝑖ℎ −1) , ℎ (𝜌𝑣1 (𝑖ℎ + 1)) + 𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝜌𝑣1 (𝑖ℎ + 1))}. (4.3)
1
Similarly to ℎ′1 (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒), the quantity ℎ′2 (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) is estimated as the
maximum tardiness of the jobs belonging to one of the following customers:
(𝑖) the customer preceding 𝑘 in 𝜌𝑣2 , (𝑖𝑖) customer ℎ, (𝑖𝑖𝑖) customer 𝑘 and (𝑖𝑣)
all the customers following 𝑘 in 𝜌𝑣2 . The new head of customer 𝜌𝑣2 (𝑖𝑘 − 1) is
ℎ′ (𝜌𝑣2 (𝑖𝑘 − 1)) = ℎ(𝜌𝑣2 (𝑖𝑘 − 1)) + Δ𝐸2 and its tardiness becomes 𝑇𝜌′ 𝑣 (𝑖𝑘 −1) =
2
max{0, ℎ′ (𝜌𝑣2 (𝑖𝑘 −1))+max𝑗∈𝒥 𝑉 (𝑣2 ,𝜌𝑣2 (𝑖𝑘 −1)) {𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝑗)}}. The tardiness of ℎ
becomes 𝑇ℎ′ = max{0, ℎ′ (𝜌𝑣2 (𝑖𝑘 −1))+𝑡𝜌𝑣2 (𝑖𝑘 −1)ℎ +max𝑗∈𝒥 𝑉 (𝑣1 ,ℎ) {𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝑗)}}.
The tardiness of 𝑘 and all its successors in 𝜌𝑣2 is max{0, ℎ′ (𝜌𝑣2 (𝑖𝑘 − 1)) +
𝑡𝜌𝑣2 (𝑖𝑘 −1)ℎ + 𝑡ℎ𝑘 + 𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝑘)}.
ℎ′2 (𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) = max{𝑇𝜌′ 𝑣 ′

(𝑖𝑘 −1) , 𝑇ℎ , ℎ(𝜌𝑣2 (𝑖𝑘 −1))+𝑡𝜌𝑣2 (𝑖𝑘 −1)ℎ +𝑡ℎ𝑘 +𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝑘)}.
2
(4.4)
Similar discussions hold for move 𝜓 𝐽 (𝑗, 𝑤) and for ℎ′ (𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑). At each
iteration of the tabu search, the neighbor with the smallest value of 𝑓2 (𝜌′ ) is
selected as the new incumbent, and the starting and arrival times are updated
accordingly.
4.4 Combined problem

The combined problem consists of finding a global solution 𝑊 = (𝐻, 𝜌) where
𝐻 is a solution to the scheduling problem 𝑆𝑃 and 𝜌 is a solution to the vehicle
routing problem 𝑉 𝑅𝑃 . The objective function 𝐹 (𝑊 ) is the minimization of
the overall production and distribution costs. As components of 𝐹 (𝑊 ) we
consider a linear combination of the makespan 𝐶𝑚𝑎𝑥 (𝐻) of schedule 𝐻, which
is a common surrogate of machine utilization and internal production costs, and
the cost function of the vehicle routing problem, i.e., 𝐹 (𝑊 ) = 𝜔2 𝐶𝑚𝑎𝑥 +𝑓𝑉 𝑅 (𝜌).
The parameter 𝜔2 reflect the relative importance of the makespan component
with respect to 𝑓𝑉 𝑅 (𝜌).
In this section we present two approaches studied for the resolution of this
problem. The first, decentralized, approach follows the commonly adopted de-
composition approach in which 𝑆𝑃 is solved independently from 𝑉 𝑅𝑃 . Due
dates at the customer are converted into due dates for each job in the pro-
duction scheduling problem by letting a fixed value Δ𝑑 for delivery, which is
subtracted to the due date for delivery. The completion time of each job in
the scheduling problem becomes a release time for the same job in the vehicle
routing problem.
The second, centralized, approach solves the two subproblems simultane-
ously as a single production scheduling and delivery problem 𝑆𝑃 + 𝑉 𝑅𝑃 .
Decentralized approach
In the decentralized approach the problem is decomposed into two subproblems:
∙ the scheduling problem 𝑆𝑃 ,

∙ the vehicle routing problem 𝑉 𝑅𝑃 .
𝑆𝑃 is formulated with the model described in Section 3.3 with objective

function 𝑓𝑆𝑃 (𝐻) = 𝜔 𝑇˜𝑚𝑎𝑥 + 𝜔1 𝑇𝑚𝑎𝑥 + 𝜔2 𝐶𝑚𝑎𝑥 , and solved with the version
B-D of algorithm TS described in 3.4. In order to define a due date for each
job 𝑗 ∈ 𝒥 , the due dates for delivering jobs to final customers are converted
into due dates for production scheduling by letting a fixed time Δ𝑑 for delivery,
i.e., 𝑑𝑆𝑗 = 𝑑𝑉𝑗 − Δ𝑑 where 𝑑𝑆𝑗 and 𝑑𝑉𝑗 are the due dates for SP and for 𝑉 𝑅𝑃 ,
respectively. In the second phase the vehicle routing problem 𝑉 𝑅𝑃 is solved
with the algorithm introduced in Section 4.3. The solutions of the two sub-
problems are then joined to form the solution of the combined problem.
Given the best solution 𝐻 to problem 𝑆𝑃 found by TS and the correspond-
ing vector of completion times 𝐶, problem 𝑉 𝑅𝑃 is formulated by defining
a release time 𝑒𝑗 = 𝐶 𝑗 for each job 𝑗 ∈ 𝒥 . An initial solution for VRP
is found by applying a simple constructive algorithm that assigns the first
available job in each machine in 𝐻 to an empty vehicle until the maximum
capacity 𝑄 is reached; this procedure is repeated by considering other vehi-
cles until all jobs in 𝐻 are assigned to a vehicle. Then the tabu search al-
gorithm of Section 4.3 is applied to minimize the objective function of 𝑉 𝑅𝑃 ,
𝑓𝑉 𝑅 (𝜌) = 𝜔 𝑇˜𝑚𝑎𝑥 + 𝜔1 𝑇𝑚𝑎𝑥 + 𝜔3 𝑛𝑉 + 𝜔4 𝑡𝑡𝑜𝑡 .
Letting 𝜌 be the best solution found to 𝑉 𝑅𝑃 , a solution 𝑊 = (𝐻, 𝜌) to
the combined problem is obtained by coupling the solutions of the two sub-
problems. The cost of 𝑊 is then:
𝐹 (𝑊 ) = 𝜔2 𝐶𝑚𝑎𝑥 (𝐻) + 𝑓𝑉 𝑅 (𝜌) (4.5)
Centralized approach
With the centralized approach, the scheduling problem and the vehicle routing
problem are solved simultaneously as a single combined problem. To this aim,
an integrated model has been defined and a global algorithm developed.
Model
The model adopted to represent a solution is an extension of the graph rep-
resentations used for the single sub-problems. In particular the two graph
representations are joined to form a global representation of the whole solution
(see Figure 4.2). This is done by the following simple modifications:
∙ node 𝑠𝑡𝑎𝑟𝑡 𝑑 and corresponding arcs are removed from 𝒢(𝜌)
∙ an arc (𝑗, 𝑣) is added from the node associated to job 𝑗 ∈ 𝒢(𝐻) to the
node associated to the vehicle 𝑣 for each 𝑗 ∈ 𝒥 𝑉 (𝑣).
The resulting graph is denoted with 𝒢(𝑊 ).
Figure 4.2: Graph model for the centralized resolution approach for the com-
bined problem
Neighborhood definition and exploration

In this section we briefly describe the tabu search algorithm we use to solve
the combined problem. The neighborhood used is the union of neighborhoods
defined for the 𝑆𝑃 and 𝑉 𝑅𝑃 . We next describe two strategies used for neigh-
borhood exploration, similar to those adopted for solving the two subproblems.
One is based on the critical path criteria, and the other randomly explores a
subset of neighbors.
The first strategy take into account critical paths in 𝒢(𝑊 ) from 𝑠𝑡𝑎𝑟𝑡 to
node 𝑒𝑛𝑑, 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 or 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑. Specifically, we consider a critical path from
𝑠𝑡𝑎𝑟𝑡 to 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑 if ℎ(𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑) > 0, otherwise a critical path from 𝑠𝑡𝑎𝑟𝑡 to
𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 if ℎ(𝑣𝑖𝑜𝑙 𝑑𝑢𝑒) > 0, otherwise a critical path from 𝑠𝑡𝑎𝑟𝑡 to 𝑒𝑛𝑑. Paths
from 𝑠𝑡𝑎𝑟𝑡 to 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑 or 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 can be divided into two paths: a path from
𝑠𝑡𝑎𝑟𝑡 to a node representing a vehicle, and a path from a node representing
a vehicle to 𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑 or 𝑣𝑖𝑜𝑙 𝑑𝑢𝑒. The first path refers to the production
scheduling component of the solution. Neighbors are therefore generated by
considering interchange and rerouting moves involving nodes in this path (see
section 3.4). The second path refers to the routing component of 𝑊 . Other
neighbors are therefore generated by considering reroutingC and reroutingJ
moves involving nodes in this path (see section 4.3). Finally, nodes in the
critical path from 𝑠𝑡𝑎𝑟𝑡 to 𝑒𝑛𝑑 are used to generate other neighbors with the
interchange and rerouting moves.
The random exploration is the same described in Section 4.3.
Move evaluation
The objective function of the combined problem is defined as:
𝐹 (𝑊 ) = 𝜔 𝑇˜𝑚𝑎𝑥 + 𝜔1 𝑇𝑚𝑎𝑥 + 𝜔2 𝐶𝑚𝑎𝑥 + 𝜔3 𝑛𝑉 + 𝜔4 𝑡𝑡𝑜𝑡 (4.6)
with 𝑇˜𝑚𝑎𝑥 = max{0, ℎ(𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑)} and 𝑇𝑚𝑎𝑥 = max{0, ℎ(𝑣𝑖𝑜𝑙 𝑑𝑢𝑒)}. Sim-
ilarly to the tabu search algorithm for the VRP problem, the exploration of
infeasible solutions is allowed in order to search for more effective solutions, and
infeasible solutions are penalized. The function used to evaluate the neighbor-
hood of the incumbent solution 𝜌, is the following:
𝐹2 (𝑊 ) = 𝐹 (𝑊 ) + 𝜔5 𝑠𝑡𝑜𝑡 (4.7)
Depending on the chosen move, only some quantities in Equation (4.7) can
vary after move implementation. In particular, 𝐶𝑚𝑎𝑥 can only vary after an
interchange move or a rerouting move, 𝑛𝑉 ,𝑠𝑡𝑜𝑡 and 𝑡𝑡𝑜𝑡 can only vary after a
reroutingC or a reroutingJ move, while 𝑇˜𝑚𝑎𝑥 and 𝑇𝑚𝑎𝑥 can vary after any move.
When a reroutingC or a reroutingJ move is applied, quantities 𝑛𝑉 ,𝑠𝑡𝑜𝑡 ,𝑡𝑡𝑜𝑡 are
calculated exactly, while for 𝑇˜𝑚𝑎𝑥 and 𝑇𝑚𝑎𝑥 an estimate is calculated as in
Section 4.3.
Let us now consider the interchange and rerouting moves. 𝐶𝑚𝑎𝑥 is calcu-
lated exactly as in Section 3.4. For the estimate of 𝑇˜𝑚𝑎𝑥 and 𝑇𝑚𝑎𝑥 there is
one significant difference with the decentralized case. In fact, in the central-
ized case any change to the production schedule directly affects the solution of
the vehicle routing problem. In order to take into account the global effects
on 𝑇˜𝑚𝑎𝑥 and 𝑇𝑚𝑎𝑥 of the interchange moves 𝜑𝑀 (𝑖, 𝑗) and 𝜑𝑇 (𝑖, 𝑗), and of the
rerouting move 𝜃𝑀 (𝑖, 𝑗), an exact computation of the new heads is performed
for the scheduling part of the graph in order to evaluate exactly the release
time 𝐸𝑣′ of each vehicle 𝑣 ∈ 𝒱. This computation is performed at no extra cost
since the new heads of these nodes are evaluated exactly for the estimation
of 𝐶𝑚𝑎𝑥 . Since the tails of vehicle nodes are unchanged when passing from
𝒢(𝑊 ) to 𝒢(𝑊 ′ ), 𝑇˜𝑚𝑎𝑥 becomes 𝑇˜𝑚𝑎𝑥 = max𝑣∈𝒱 {𝐸𝑣′ + 𝑞𝑣𝑖𝑜𝑙 𝑑𝑒𝑎𝑑 (𝑣)}, while
𝑇𝑚𝑎𝑥 = max𝑣∈𝒱 {𝐸𝑣′ + 𝑞𝑣𝑖𝑜𝑙 𝑑𝑢𝑒 (𝑣)}.
4.5 Computational experiments

This section reports on the performance of the two resolution approaches for
the combined problem and compares the corresponding results. For all exper-
iments, the parameters in the objective functions 𝐹 (𝑊 ) and 𝐹 (𝑊 ) are set as
follows: 𝜔 = 1010 , 𝜔1 = 10, 𝜔2 = 1, 𝜔3 = 102 and 𝜔4 = 1. As for 𝜔5 , this

parameter varies dynamically during the execution of the algorithm, as in [14].
The algorithms are coded in C language and run on a Pentium⃝ R
4, 3.0 GHz
with 1024 MB Ram. The testbed for the experiments contains the 24 realis-
tic instances described in Section 3.5 for the production scheduling problem,
divided in three groups of easy, medium and hard instances. The instances
have been extended by adding a vehicle routing part. A customer is randomly
associated to each job and the number 𝑐 of customers is set 𝑐 = 𝑛/2, so that
an average of 2 jobs is delivered to each customer. Then, each customer is as-
signed to one out of 15 Italian cities. Table in Figure 4.3 reports the distances
(in km) between the cities and the depot. For all vehicles an average speed of
60𝑘𝑚/ℎ is considered. The difference between the due dates/deadlines for the
vehicle routing problem and for the scheduling problem are fixed equal to 48
hours for each job. The capacity of each vehicle is 𝑄 = 10.
Figure 4.3: Distances between customer locations (km)
Tables 4.1 and 4.2 show the results obtained with the decentralized and
centralized approach, respectively. Each row in the tables reports the average
results over eight instances. Column 2 reports the average computation time
(in seconds) required to find the best solution to a problem instance.
It can be observed from tables 4.1 and 4.2 that the centralized approach
provides much better results than the decentralized one. The improvement is
particularly important for the hard instances, for which there are two instances
over eight for which the decentralized approach is not able to find a solution
without violating some deadlines (see the very high values in columns 𝐹 (𝑊 )
and 𝐹 (𝑊 ) of tables 4.1 and 4.3, respectively, due to the high value of the
penalization constant 𝜔 in the corresponding objective functions). This result
confirms the need for good coordination among different stages of the produc-
tion process when high standards of quality and reliability must be provided to
the final customers. The algorithm proposed is very promising in this respect
since effective solutions to practical size instances of the combined problem are
provided within less than a minute of computation.
Table 4.1: Test for decentralized approach

Decentralized
Instance 𝑡𝑖𝑚𝑒 𝐹 (𝑊 ) 𝐶𝑚𝑎𝑥 𝑇˜𝑚𝑎𝑥 𝑇𝑚𝑎𝑥 𝑛𝑣 𝑡𝑡𝑜𝑡
Difficult 57.0 973751461.5 254.8 0.97 56.0 4.6 177.7
Medium 55.6 1173.9 256.4 0 40.3 3.6 151.8
Easy 63.6 637.9 234.0 0 0 3 103.9
Table 4.2: Test for centralized approach

Centralized
Instance 𝑡𝑖𝑚𝑒 𝐹 (𝑊 ) 𝐶𝑚𝑎𝑥 𝑇˜𝑚𝑎𝑥 𝑇𝑚𝑎𝑥 𝑛𝑣 𝑡𝑡𝑜𝑡
Difficult 38.9 777.7 242.5 0 0 3.1 222.7
Medium 27.5 761.8 246.7 0 0 3.0 215.1
Easy 30.9 630.8 226.4 0 0 3.0 104.4
Tables 4.3, 4.4 and 4.5 show the results obtained with the centralized ap-
proach when using different neighborhood structures and refer to difficult,
medium and easy instances, respectively. Each row in the tables reports
the average results over eight instances. This second set of experiments aims
to demonstrate the effectiveness of the different neighborhood structures. In
columns 2 and 3 we show the number of iterations and the computation time
(in seconds) of the tabu search to find the best solution.
It can be observed that the Critical Path neighborhood (CP) is particu-
larly effective for the minimization of the minmax components in the objective
function (𝐶𝑚𝑎𝑥 , 𝑇˜𝑚𝑎𝑥 and 𝑇𝑚𝑎𝑥 ) while the random neighborhood is particu-
larly effective with the minsum components (𝑛𝑣 and 𝑡𝑡𝑜𝑡 ). However, the joint
Table 4.3: Centralized approach with different neighborhoods

Difficult instances
Neighborhood 𝑖𝑡𝑒𝑟 𝑡𝑖𝑚𝑒 𝐹 (𝑊 ) 𝐶𝑚𝑎𝑥 𝑇˜𝑚𝑎𝑥 𝑇𝑚𝑎𝑥 𝑛𝑣 𝑡𝑡𝑜𝑡
CP+Random VR 63.4 38.9 777.7 242.5 0 0 3.1 222.7
Random VR 40.7 5.1 9528750821.0 314.9 9.5 0 3.1 196.1
CP 68.5 28.4 920.9 240.1 0 0 4.5 230.8
use of both neighborhoods is more effective than any of the two stand alone
neighborhoods.

Medium instances
CP+Random VR 18.9 27.5 761.8 246.7 0 0 3.0 215.1
Random VR 23.7 4.9 855.2 349.2 0 0 3.0 205.9
CP 18.9 29.6 761.8 246.7 0 0 3.0 215.1

Easy instances
CP+Random VR 584.6 30.9 630.8 226.4 0 0 3.0 104.4
Random VR 128.0 5.2 653.1 245.2 0 0 3.0 107.9
CP 134.5 20.9 740.3 223.6 0 0 3.0 216.7
Conclusion
This thesis deals with production scheduling in pharmaceutical industry. Man-

ufacturing process in this industry is characterized by an high complexity of
processes. This is due to various reasons as the complexity of chemical and
biochemical procedures at the basis of the whole production process, cross-
contamination that has to be avoided in order to guarantee the quality of
products and finally the need of specialized man-power for the different op-
erations. Moreover, compared to other manufacturing industry, the pharma-
ceutical industry gives higher importance to on-time delivery over throughput
maximization, due to the economical and legal implications of late deliveries
and stock-outs at the final customers. Hence, given the complexity of manufac-
turing processes and the issue of on-time delivery, it can happen that produc-
tion plans released in the planning stage are not sustainable by the production
capacity. In this situation, it is evident that scheduling stage is a critical op-
eration and so, that an automated scheduling system is important, both to
obtain good scheduling solutions and to have a better control of the produc-
tion process. A case study of production scheduling, concerning the packaging
department in a real pharmaceutical industry, has been analyzed in this thesis.
A complex model and a tabu search algorithm have been developed to solve the
related multi-purpose machine scheduling problem. Our tabu search algorithm
is able to find good solutions within short computation time, compared to the
solutions found by human schedulers. These results confirm that scheduling
technology is mature to solve complex real problems; to this aim, however, it
is important to face the complexity of practical scheduling problems by using
detailed scheduling models.
Possible future developments of this research line could involve:
∙ the inclusion of further details in the scheduling problem as the transport

time of tools from a machine to another one;
64
CONCLUSION 65
∙ the development of a more sophisticated tabu search algorithm, featuring

advanced instruments as a dynamic tabu list size or diversification and
intensification techniques;
The second topic studied in thesis has been the coordination between schedul-
ing and distribution stages in the pharmaceutical production. The need for
coordination arises from the observation that decisions made in a stage of the
supply chain can result in inconvenient decisions for the following stages: co-
ordination might enable to take decisions that are globally more convenient
for the whole system. Coordination issues are particularly important in the
pharmaceutical supply chain, in which the legal and economical implications
of product stock-out requires the adoption of standards of product quality and
availability close to 100%. Availability of final products requires not only to
achieve excellence at each stage of the planning process, from strategic plan-
ning to real time scheduling and delivery, but also in the coordination between
different stages. The need for coordination is more evident in departments
that operates as pull systems as the packaging and distribution departments.
The object of the second case study of this thesis has been the coordination
between these two departments of the real pharmaceutical industry taken into
account in the first case study. The aim of the study has been to investigate
on the benefits that the introduction of a centralized decision support system
can bring with respect to a decentralized one. Results have demonstrated that
the centralized approach provides much better results than the decentralized
one with even a less computational effort. These results confirm the need for
excellence in the coordination among different stages of the production process,
other than within each stage, when high standards of quality and reliability
must be provided to the final customers.
Future research should be dedicated to the coordination of scheduling de-
cisions among a larger number of departments. Following this research line,
the manufacturing department could be included in the centralized approach,
as well as the planning department or the marketing department. In fact the
two latter departments determine the amount of work and the due dates to
be met by the scheduling function. More detailed models for the distribution
problem could also take into account the addition of other practical constraints
as work-shifts and limited availability of human operators. Also the problem of
managing the inventory between scheduling and distribution might be consid-
ered in these models, from the viewpoint of both the cost of inventory and the
space available for storing finished products. From the perspective of solution
techniques, there is a lot of space for the development of more sophisticated
CONCLUSION 66
centralized techniques. Also the development of more effective decentralized

techniques is a promising direction that needs further development. Following
this research line, the coordination between the departments should not be lim-
ited to the simple communication of products completion times from packaging
to distribution, but the two departments might negotiate completion times for
the packaging department that enable the distribution department to improve
the overall performance.
Bibliography
[1] B. Adenso-Dı́az and M. Laguna. Fine-tuning of algorithms using fractional

experimental designs and local search. Operations Research, 54:99–114,
2006. [cited at p. 42]
[2] A. Agnetis, P. Detti, C. Meloni, and D. Pacciarelli. Set-up coordination
between two stages of a supply chain. Annals of Operations Research,
107:15:32, 2001. [cited at p. 50]
[3] O. Braysy. A reactive variable neighborhood search for the vehicle-
routing problem with time windows. INFORMS Journal on Computing,
15(4):347–368, 2003. [cited at p. 27]
[4] O. Braysy and M. Gendreau. Vehicle routing problem with time win-
dows, part ii: Metaheuristics. Transportation Science, 39(1):119–139,
2005. [cited at p. 27]
[5] P. Brucker. Scheduling Algorithms, 5th edition. Springer, 2007.
[cited at p. 10]
[6] P. Brucker, A. Drexl, R. Mohring, K. Neumann, and E. Pesch. Resource-

constrained project scheduling: Notation, classification, models, and
methods. European Journal of Operational Research, 112(1):3–41, 1999.
[cited at p. 27]
[7] P. Brucker and S. Knust. Complex scheduling. Springer, 2006. [cited at p. 10]
[8] Z. Chen and G. L. Vairaktarakis. Integrated Scheduling of Production

and Distribution Operations. Management Science, 51:614–628, 2005.
[cited at p. 50]
67
BIBLIOGRAPHY 68
[9] W.C. Chiang and R.A. Russell. A reactive tabu search metaheuristic for
the vehicle routing problem with time windows. INFORMS Journal on
Computing, 9(4):417–430, 1997. [cited at p. 27, 34]
[10] G. C. Cole. Pharmaceutical production facilities. Design and applications,
2nd edition. CRC Press, 1998. [cited at p. 2, 3, 5]
[11] S. Dauzère-Pérès, W. Roux, and J.B. Lasserre. Multi-resource shop
scheduling with resource flexibility. European Journal of Operational Re-
search, 107(2):289–305, 1998. [cited at p. 35, 36]
[12] M. Dell’Amico and M. Trubian. Applying tabu search to the job-shop
scheduling problem. Annals of Operations Research, 41:231–252, 1993.
[cited at p. 16]
[13] P. M. França, M. Gendreau, G. Laporte, and F. M. Muller. A tabu search

heuristic for the multiprocessor scheduling problem with sequence depen-
dent setup times. International Journal of Production Economics, 43:78–
89, 1996. [cited at p. 13, 34]
[14] M. Gendreau, A. Hertz, and G. Laporte. A Tabu Search Heuristic for
the Vehicle Routing Problem. Management Science, 40:1276–1290, 1994.
[cited at p. 52, 61]
[15] F. Glover. Future paths for integer programming and links to artifi-
cial intelligence. Computers and operations research, 13:533–549, 1986.
[cited at p. 11]
[16] F. Glover and M. Laguna. Tabu Search. Kluwer, 1997. [cited at p. 11]
[17] J. Grabowski, E. Nowicki, and S. Zdrzalka. A block approach for single-

machine scheduling with release dates and due dates. European Journal
of Operational Research, 26(2):278–285, 1986. [cited at p. 16]
[18] J. Grabowski, E. Skubalska, and C. Smutnicki. On Flow Shop Scheduling
with Release and Due Dates to Minimize Maximum Lateness. The Journal
of the Operational Research Society, 34:615–620, 1983. [cited at p. 16]
[19] J. Grabowsky and M.Wodecki. A very fast tabu search algorithm for job
shop problem. Metaheuristics Optimization via Memory an Evolution,
Tabu Search and Scatter Search,Kluwer, 2004. [cited at p. 16]
BIBLIOGRAPHY 69
[20] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan.

Optimization and approximation in deterministic machine scheduling: a
survey. Annals of Discrete Mathematics, 5:287–326, 1979. [cited at p. 11]
[21] N.G. Hall and C.N. Potts. Supply chain scheduling: batching and delivery.
Operations Research, pages 566–584, 2002. [cited at p. 50]
[22] S. Hartmann, R. Kolisch, S. Hartmann, Dr. R. Kolisch, and Lehrstuhl
Fur Produktion Und Logistik. Experimental evaluation of state-of-the-art
heuristics for the resourc-constrained project scheduling problem. Euro-
pean Journal of Operational Research, 127:394–407, 1998. [cited at p. 24]
[23] J. Hurink, B. Jurisch, and M. Thole. Tabu search for the job shop schedul-
ing problem with multi-purpose machines. OR Spektrum, 15:205–215,
1994. [cited at p. 21]
[24] A.P Hurter and M.G. Van Buer. The newspaper production/distribution
problem. Journal of Business Logistics, 17(1):85–107, 1996. [cited at p. 50]
[25] R. Kolisch and S Hartmann. Heuristic algorithms for solving the resource-
constrained project scheduling problem: classification and computational
analysis. Handbook of recent advances in project scheduling, Boston:
Kluwer Academic Publishers., 141:147–178, 1998. [cited at p. 24]
[26] R. Kolisch and S. Hartmann. Experimental investigation of heuristics for
resource-constrained project scheduling: An update. European Journal of
Operational Research, 174(1):23–37, 2006. [cited at p. 24]
[27] K.L. Mak and Y.S. Wong. Design of integrated production-inventory-
distribution systems using genetic algorithm. Proceedings of the 1st
IEE/IEEE International Conference on Genetic Algorithms in Engi-
neering Systems: Innovations and Applications, 414:454–460, 1995.
[cited at p. 50]
[28] A. Mascis and D. Pacciarelli. Machine scheduling via alternative graphs.

Report DIA-46-2000, University of Rome, Italy, 2000. [cited at p. 20]
[29] A. Mascis and D. Pacciarelli. Job-shop scheduling with blocking and no-
wait constraints. European Journal of Operational Research 143, 103:498–
517., 2002. [cited at p. 20]
BIBLIOGRAPHY 70
[30] M. Mastrolilli and L.M. Gambardella. Effective neighbourhood functions

for the flexible job shop problem. Journal of Scheduling, 3:3–20, 2000.
[cited at p. 22]
[31] K.N. McKay, M. Pinedo, and S. Webster. Practice-focused research issues

for scheduling systems. Production and Operations Management, 11:249–
258, 2002. [cited at p. 26]
[32] K.N. McKay and V. C. S. Wiers. Integrated decision support for planning,
scheduling, and dispatching tasks in a focused factory. Computers In
Industry, 50:5–14, 2003. [cited at p. 26]
[33] T. E. Morton and D. W. Pentico. Heuristic Scheduling Systems. John
Wiley & Sons, 1993. [cited at p. 10]
[34] E. Nowicki and C. Smutnicki. A fast tabu search algorith for the job shop
problem. Management Science, 42(6), 1996. [cited at p. 17]
[35] E. Nowicki and C. Smutnicki. A fast tabu search algorithm for the per-
mutation flow-shop problem. European Journal of Operational Research,
91:160–175, 1996. [cited at p. 16, 17, 18]
[36] E. Nowicki and C. Smutnicki. An advanced tabu search algorithm for the
job shop problem. Journal of Scheduling, 8:145–159, 2005. [cited at p. 13, 17,
34, 38]
[37] D. Pacciarelli. The alternative graph formulation for solving complex fac-
tory scheduling problems. International Journal of Production Research,
40:3641–3653, 2002. [cited at p. 9]
[38] D. Pacciarelli, C. Meloni, and M. Pranzo. Models and methods for pro-
duction scheduling in pharmaceutical industry. In J. Weglarz, editor, K.
Kempf, P. Keskinocak, and R. Uzsoy (Eds.) Handbook of Production Plan-
ning,Kluwer International Series in Operation Research and Management
Science. Kluwer, 2009. [cited at p. 7]
[39] B. Piachaud. Outsourcing of R&D in the Pharmaceutical Industry : From
Conceptualization to Implementation of the Strategic Sourcing Process.
Palgrave Macmillan, 2005. [cited at p. 5]
[40] M. Pinedo. Scheduling. Theory, algorithms, and systems. Prentice-Hall,
1995. [cited at p. 9, 28]
BIBLIOGRAPHY 71
[41] M. Pinedo. Planning and Scheduling in Manufacturing and Services.

Springer, 2005. [cited at p. 9]
[42] A. Reisman, A. Kumar, and J. Motwani. Flowshop scheduling/sequencing
research: a statistical review of the literature, 1952–1994. IEEE Transac-
tions on Engineering Management, 44:316–329, 1997. [cited at p. 9]
[43] B. Roy and B. Sussmann. Les problems d’ordonnancements avec con-
straintes disjonctif. Node DS 9 bis, SEMA, Montrouge, 1964. [cited at p. 14]
[44] R.K. Roy. A Primer on the Taguchi Method. Van Nostrand Reinhold,
New York, 1990. [cited at p. 42]
[45] R. Ruiz, F.S. Şerifoğlu, and T. Urlings. Modeling realistic hybrid flexi-
ble flowshop scheduling problems. Computers and Operations Research,
35:1151–1175, 2008. [cited at p. 9]
[46] R. Russella, W.-C. Chianga, and D.Zepedab. Integrating multi-product
production and distribution in newspaper logistics. Computers & Opera-
tions Research, 35:1576–1588, 2008. [cited at p. 50]
[47] A.M. Sarmiento and R. Nagi. A review of integrated analysis of
production-distribution systems. IIE Transactions, 31(11):1061–1074,
1999. [cited at p. 50]
[48] J. M. J. Schutten and R. A. M. Leussink. Parallel machine scheduling with
release dates, due dates and family setup times. International Journal of
Production Economics, 46:119–125, 1996. [cited at p. 27]
[49] N. Shah. Pharmaceutical supply chains: key issues and strategies for
optimisation. Computers and Chemical Engineering, 28:929–941, 2004.
[cited at p. 2, 5]
[50] H. Stefansson and N. Shah. Multi-scale planning and scheduling in the

pharmaceutical industry. L. Puigjaner and A. Espuna (eds.),European
Symposium on Computer Aided Process Engineering, Elsevier, 2, 2005.
[cited at p. 50]
[51] V. T’kindt and J.C. Billaut. Multicriteria Scheduling. Springer, 2006.

[cited at p. 26]
BIBLIOGRAPHY 72
[52] P. J. M. van Laarhoven, E. H. L. Aarts, and J. K. Lenstra. Job

Shop Scheduling by Simulated Annealing. OPERATIONS RESEARCH,
40(1):113–125, 1992. [cited at p. 15]
[53] L. Venditti, D. Pacciarelli, and C. Meloni. A tabu search algorithm for
scheduling pharmaceutical packaging operations. European Journal of Op-
erational Research, 202. [cited at p. 27]
[54] G.H. Vieira, J.W. Herrmann, and E. Lin. Rescheduling manufacturing
systems: a framework of strategies, policies, and methods. Journal of
Scheduling, 6:39–62, 2003. [cited at p. 26]

377e PDF

Uploaded by

Copyright:

Available Formats

377e PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

377e PDF

Uploaded by

Copyright:

Available Formats

ROMA

Roma Tre University

Production scheduling is the phase of production management that produces

Besides operations management in a single stage, another interesting issue

This thesis is organized as follows:

1. In Chapter 1 the production scheduling in the pharmaceutical industry

1 Production scheduling: the pharmaceutical industry 1

2 Literature on scheduling problems: from theory to practice 9

3 Case study 1: A Tabu Search algorithm for production schedul-

4 Coordination of production scheduling and distribution in a

3.1 Comparison between manual and computerized schedules . . . . . 44

4.1 Test for decentralized approach . . . . . . . . . . . . . . . . . . . . 62

1.1 The pharmaceutical supply chain . . . . . . . . . . . . . . . . . . . 4

3.1 Gantt chart for machines ℎ and ℎ′ and computation of 𝑆𝑗 . . . . . 30

4.1 Graph model for the distribution problem . . . . . . . . . . . . . . 53

Production scheduling: the

Production scheduling is the phase of production management that produces a

1.1 Pharmaceutical manufacturing systems

From the point of view of production scheduling, it is more interesting to

Common production processes are devoted to producing solid, liquid, aerosol

∙ Dispensing, where, with respect to the receipt, the availability of all

Figure 1.1: The pharmaceutical supply chain

∙ Manufacturing, where most of activities are performed, i.e.: speciﬁc

Figure 1.2: Typical layout of a secondary pharmaceutical manufacturing plant

Some common features of all departments are:

1. single-product processing, i.e. one product at a time is processed in the

These features require incorporation of a number of relevant details into

1.2 An example of pharmaceutical plant

Packaging and Distribution

The Distribution department is the ﬁnal department of the chain. Resources

in literature, are ﬁrst presented; in a second analysis, some generalizations of

The remainder of this chapter is structured as follows. In Section 2.2 some

2.2 Basic deﬁnitions

∙ a processing time 𝑝𝑖𝑗 required to process task 𝑖 of job 𝐽𝑗

∙ a deadline 𝐷𝑗 within which job 𝐽𝑗 must be completed

Classes of scheduling problems are speciﬁed in terms of a three-ﬁeld classi-

2.3 Tabu Search

optimization algorithm, in order to be eﬀective and eﬃcient, must provide a

2.4 Shop scheduling problems

𝑀1 , . . . , 𝑀𝑚 and a set 𝒥 of 𝑛 jobs 𝐽1 , . . . , 𝐽𝑛 are given. Job 𝐽𝑗 consists of 𝑛𝑗

if a direction has been ﬁxed for each disjunction in 𝐷; moreover, 𝒮 is called

Heuristic and meta-heuristics: local search and tabu search

the optimal makespan, 𝒮 must be optimal. Neighborhood 𝑁𝑐𝑎 is proved to

Concerning neighborhood evaluation, in order to determine the best neigh-

property has been proved [35]:

2.5 Generalized shop scheduling problems

Flexible Job Shop

Neighborhoods for local and tabu search

Job-Shop Problems with Transport Times

General shop problems with machine dependent removal and

2.6 Multi-resource constrained scheduling problems

Local search and tabu search

∙ The adjacent pairwise interchange-neighborhood. This neighbor-

Case study 1: A Tabu Search

In this chapter, we address the problem of scheduling packaging operations

The remainder of this chapter is organized as follows. In Section 3.2 a

3.2 Description of the problem

𝑂𝑀 𝑃 𝑀 ∣𝑟𝑖 , 𝑑𝑖 , 𝐷𝑖 , 𝑅𝑠𝑑 , 𝑆𝑠𝑑 , 𝑢𝑛𝑎𝑣𝑎𝑖𝑙𝑗 ∣𝐿𝑒𝑥(𝐶𝑚𝑎𝑥 , 𝑇𝑚𝑎𝑥 )

Concerning the shop environment, 𝑂𝑀 𝑃 𝑀 is the Open shop Multi-Purpose