Introduction to scheduling of

batch processes

Prof. Cesar de Prada

ISA-UVA
prada@[Link]
Outline
 Batch processes and batch plants
 Basic concepts of scheduling
 How to formulate scheduling problems
 Solution with optimization tools
Batch plants
 As the demand of high added value products of
limited production (fine-chemicals, pharmaceuticals,
food, certain polymers,….) is growing, the interest
for batch plants in the process industry has increased
 In the same direction, the concept of multiproduct
flexible production, where the equipment is re-used
in order to manufacture different products according
to a demand-driven scheme, has risen this interest.
 The use of batch processes requires a careful
production planning and scheduling, that determines
which products must be manufactured or processed,
in which process units, in what order as well as the
starting and ending times in each process unit.
Batch units
Operation

Load
Sequence of
internal
operation and
stages in the
unit
Unload
Recipe for the
operation

Basically, control
problems
Operation of batch plants

When a firm operates with

batch units, a key problem is
to determine when each one
should be started and
unloaded and which products
must process, so that a
certain amount of products is
manufactured satisfying
constraints on energy, quality,
storage space, etc, and
optimizing some adequate
criterion.
 Single product manufacturing
Usually the manufacturing of a product implies several stages
that take place in different batch process units according to a
certain recipe.
Example:

Mixer
Centrifugal A
Reactor Drying
U2 U3
U1 U4

Stage 1, 4 h Stage 2, 1 h Stage 3, 2 h Stage 4, 1 h

In the example, manufacturing of product A cover four successive

stages (each one in a different batch unit, lasting the indicated times )
Gantt diagram

U1 1
U2 2
U3 3
U4 4

0 2 4 6 8 10 12 14 16 t (hr)

U1 1 Transfer of
U2 2 product between
U3 3 units
U4 4

0 2 4 6 8 10 12 14 16 t (hr)
Gantt diagram
Non overlaped
U1 1 1
operation
U2 2 2
U3 3 3
U4 4 4

0 2 4 6 8 10 12 14 16 t (hr)

U1 1 1 Overlaped operation
U2 2 2
U3 3 3
U4 4 4

0 2 4 6 8 10 12 14 16 t (hr)
 Cycle Time
Cycle time = 8 h
M
tc = ∑ τj
U1 1 1
U2 2 2
j=1
U3 3 3
U4 4 4
M=
0 2 4 6 8 10 12 14 16 t (hr) number of
Cycle time = 4 h stages

U1 1 1 t c = max{τ j }
U2 2 2 j=1, M

U3 3 3
U4 4 4

0 2 4 6 8 10 12 14 16 t (hr)

Time interval between the start of two consecutive cycles

 Cycle Time
Another example. Notice the duration of stages 1 and 2
Processing times in the batch units:
U1= 2h , U2 = 3h, U3 = 2h, U4 = 1h No product storage

Cycle time = 3 h t c = max{τ j }

j=1, M
U1 1 1
U2 2 2 M number of
U3 3 3
stages
U4 4 4

0 2 4 6 8 10 12 14 16 t (hr)

Makespan = 11 h

Makespan: Total time required to produce a certain number of lots (example 2)

 Multiple products manufacturing
Flowshop plant: Each product follows all stages in the same order
(multiproduct plant )
Mixer
4h 1h Centrifugal 2 h 1h A
Reactor Dryer
U2 U3
U1 2h 3h 2h U4 2h
B
Jobshop plant: Not all products use all stages or follow the same
sequence (multipurpose plants)

Mixer
A
Centrifugal
Reactor Dryer
U2 U3
U1 U4
B
4h 2h 1h 2h 1h 3h
 Multiproduct manufacturing
Each stage can have one or
several batch units in parallel Several units or machines in
Single unit or machine a Single-stage manufacture

Flow-shop with Parallel units and

Multi-stage manufacturing Job-shop

1
2 A B C 3

All products use all stages following Not all products use all stages or
the same sequence follow the same sequence
 Example, two products

U1 1 1 1 1
U2 2 2 2 2
U3 3 3 3 3
U4 4 4 4 4

0 2 4 6 8 10 12 14 16 t (hr)

Campaign: manufacturing of a certain number of lots of

the different products
Example: Campaign AABB
 Types of Campaigns
Campaign cycle time 13h single product campaign SPC

U1 1 1 1 1
AABB
makespan
U2 2 2 2 2
3 3
20 h
U3 3 3
U4 4 4 4 4

0 2 4 6 8 10 12 14 16 20 t (hr)

Campaign cycle time 12h mixed product campaign MPC

ABAB
U1 1 1 1 1 makespan
U2 2 2 2 2 19 h
U3 3 3 3 3
U4 4 4 4 4

0 2 4 6 8 10 12 14 16 19 t (hr)
 Types of Campaigns
Generally speaking mix product campaigns are more efficient
that single product ones, but this will depend on the cleaning
times associated to the switching of products (changeovers)

U1 1 1 1 1
U2 2 2 2 2
U3 3 3 3 3
U4 4 4 4 4

0 2 4 6 8 10 12 14 16 20 t (hr)

Changeovers: fix, unit

dependent, frequency
U1 1 1 1 1
dependent, product
U2 2 2 2 2 dependent…
U3 3 3 3 3

U4 4 4 4 4

0 2 4 6 8 10 12 14 16 20 t (hr)
 Storage types
•No waiting time: There is no
U1 1 intermediate product storage and,
U2 2 once finished, the product cannot
U3 3 be maintained in the unit (ZW
U4 4 zero wait)
0 2 4 6 8 t (hr) •Unlimited Intermediate Storage:
There exist intermediate storage
•Storage in the same unit: tanks of unlimited capacity (UIS
There are no intermediate unlimited intermediate storage) or
storage tanks but the product finite capacity (FIS Finite
can be kept in the same unit Intermediate Storage) (shared or
in which it was processed (NIS not)
non-intermediate storage
N
ni, # of lots of
t c = max ∑ n i τij product i M, #
of stages
j=1, M
i =1
 Example
Product Stage 1 Stage 2 stage 3 Campaign ABAB
A 6 4 3
B 3 2 2

Cycle time 11h

U1 1 1 1 1
U2 2 2 2 2
U3 3 3 3 3

0 2 4 6 8 10 12 14 16 t (hr)

ZW Zero wait transfer

 Example
Cycle time 10h Storage in the unit NIS, storage in
the unit
U1 1 1 1 1
U2 2 2 2 2
U3 3 3 3 3

0 2 4 6 8 10 12 14 16 t (hr)

Cycle time 9h UIS unlimited

intermediate
U1 1 1 1 1
storage
U2 2 2 2 2
U3 3 3 3 3

0 2 4 6 8 10 12 14 16 t (hr)

tanks
Parallel units

Reactor
U1
2h
6h
U2

The products can

Reactor
U1
be processed in
several parallel
units in some
stages
Parallel units
Cycle time 6 h
ZW
U1 1 1
U2 2 2

0 2 4 6 8 10 12 14 16 t (hr)

Without parallel units

U11 ZW
1 1
U12 1 1
U2 2 2 2 2
Cycle time 4 h

0 2 4 6 8 10 12 14 16 t (hr)

With two parallel units in stage 1

 Shared resources

Processing tasks require utilities such as steam, electricity, cooling

water, etc. and manpower that are shared among the different process
units.

Besides the efficient allocation of task to units to meet product

demands, it is also necessary to consider that simultaneously
executed tasks do not to utilize resources outside their availability limits
 Planning and scheduling
Scheduling translates the economic
plan into a sequence of actions to
be executed on the factory
Months, years
Planning
Economy

Hours, days, weeks Feasibility

Scheduling Fulfilment of demand

New tools:
Seconds, minutes Information
Control systems, ERP, MES
Dynamic performance + RTO

Hierarchical decision making with different time scales,

models and incertitude
Planning and Scheduling
Planning: Allocate production of
different products to different
facilities in each time period over a
medium-term horizon to fulfil
customer demand, taking into
account capacity constraints,
inventory and transportation costs
with the aim of minimizing total cost.

Scheduling: Allocate resources (equipment,

utilities, people) to competing tasks and the
sequencing of tasks to units of a single
facility over a short-term horizon, using
more detailed information with the aim of
minimizing makespan, tardiness,…fulfilling
production targets and constraints.
Logistics
Logistics: How to store, transport
and distribute goods and
resources over time to satisfy

ao
Gijón

lb
Coruña

Bi

a
on
customers demands and supply

pl
nd

m
ira

Pa
M
León

constraints minimizing costs

Pa
Vigo Gerona
San Adrián

lle
já
os
Palencia Lérida
Zaragoza
Burg

Supply chains: a network

Barcelona
Valladolid
Tarragona

between a company and its

Salamanca
Castellón
Mahón

suppliers to produce and

Madrid
cete
ar

Valencia
Alcáz

Mora
Alba

Mérida
Ibiza Palma distribute a specific product to the
final consumer
var
Almodó Puertollano
Alicante

Sevilla Córdoba
Huelva Cartagena
Coria El Arahal
Motril Material flow
Rota Málaga End
Information flow
Algeciras (Orders) consumers
Plant Plant Distr. Retailer Demand for
Warehouse Center
A

Demand for
B

Making of
Demands for
A, B & C
C
 Planning and scheduling
 Planning and Scheduling
 Strong industrial interest

 Room for optimization

 Components: Resources (equipment, utilities,

people, materials,...), tasks (reactions, packing,

cleaning, transportation,…) and time
 Problems:
 How to formulate the operation of the system as an

optimization problem including logic and constraints

 How to solve efficiently the optimization problem

 How to interpret and implement the solution

 Mathematical Programming
 Main decision variables (real or binary):
 Resources (units, utilities, people,…) to
execute tasks at certain times
 Amount of materials processed in each task
 Inventory levels of materials over time
 Sequence of tasks
 Timing of tasks
 ….
Gantt diagram
Mathematical Programming

 Main constraints:
 Activities must proceed until completion
 Resources cannot exceed its availability
 Material balances
 Processing or storage capacity
 Satisfaction of order by its due date
 ….
 Mathematical Programming

 Typical aims:
 time required to complete all tasks (makespan)
 number of tasks completed after their due dates
 plant throughput
 Tardiness , lateness
 profit
 costs
 Time domain representation
Time slots: time intervals for allocation of tasks to units
Task
Discrete time:
U1 Slots start and
U2 end at points of
slot a fix discrete
time grid
0 2 4 6 8 10 12 14 16 t (hr)

Task Continuous time:

slots can be of
U1
any time length
U2
slot

0 2 4 6 8 10 12 14 16 t (hr)
 Discrete time representation

Tasks

U2 2 hr
U1 1.5 hr Interval = 0.5 hr
U3 3 hr
• Tasks are forced to
last an integer
• Fix number of regular intervals of time. number of
• Events can only take place at these times. discretization intervals
• Balance between problem size (number of intervals) and
approximation to reality
• Easier to formulate shared constraints
Integer variables yij
Discrete time are used to
represent if task i
U1
operates in slot j
U2
U3

0 1 2 3 4 5 6 7 8 t (hr)
 Discrete time example
Schedule the semi-batch units R so
supply p1 that levels in tanks T are maintained
within 10-90% and costs are
S minimized
F1 R1

h p2 L
T1 T2 demand

Semi-batch units F2 R2
D

F inflow to
p Batch batch units C Cost (€) Tank Initial tank Tank cross Expected supply
processing in operation per hour of volume volume section and demand may
time(h) (m3/h) processing (m3) (m3) (m2)
change every
Reactor 1 2 3.5 100
Reactor 2 3 2 140 hour according to
Tank 1 20 10 4 a table
Tank 2 22.5 12 4.5

Time (h): 1 2 3 4 5 6 7 8 9 10
Supply (m3/h) 5 5 2 6 3 5 4 3 1 0
Demand (m3/h) 2 1 5 6 7 2 2 6 4 0
 Mathematical formulation ysik = 1 if unit i
starts at time k
binary
U1 ydik = 1 if unit i
U2 Time interval = 1 h descharges at
time k binary
k
yik = 1 if unit i is
0 2 4 6 8 10 (hr) operating at time
2 10 k binary
min � � 𝐶𝐶𝑖𝑖 𝑦𝑦𝑖𝑖𝑖𝑖
𝑦𝑦,𝑦𝑦𝑦𝑦,𝑦𝑦𝑦𝑦,ℎ,𝑛𝑛 Fi flow to unit i in
𝑖𝑖=1 𝑘𝑘=1
operation
4ℎ𝑘𝑘+1 = 4ℎ𝑘𝑘 + 𝑆𝑆𝑘𝑘 − ∑2𝑖𝑖=1 𝐹𝐹𝑖𝑖 𝑦𝑦𝑖𝑖𝑖𝑖 ∀k pi batch cycle of
unit i
4𝑛𝑛𝑘𝑘+1 = 4𝑛𝑛𝑘𝑘 − 𝐷𝐷𝑘𝑘 + ∑2𝑖𝑖=1 𝑝𝑝𝑖𝑖 𝐹𝐹𝑖𝑖 𝑦𝑦𝑦𝑦𝑖𝑖𝑖𝑖 ∀k hk level of supply
tank at time k
𝑝𝑝𝑖𝑖 −1 nk level of
𝑝𝑝𝑖𝑖 𝑦𝑦𝑦𝑦𝑖𝑖𝑖𝑖 ≤ � 𝑦𝑦𝑖𝑖,𝑘𝑘+𝑗𝑗 ∀𝑖𝑖 ∀𝑘𝑘 𝑦𝑦𝑦𝑦𝑖𝑖,𝑘𝑘−𝑝𝑝𝑖𝑖 =𝑦𝑦𝑑𝑑𝑖𝑖,𝑘𝑘 ∀𝑖𝑖 ∀𝑘𝑘 discharge tank at
𝑗𝑗=0
time k
𝑝𝑝𝑖𝑖 −1 Ci cost per hour of
operation of unit i
(𝑝𝑝𝑖𝑖 − 1)(1 − 𝑦𝑦𝑦𝑦𝑖𝑖𝑖𝑖 ) ≥ � 𝑦𝑦𝑦𝑦𝑖𝑖,𝑘𝑘+𝑗𝑗 ∀𝑖𝑖 ∀𝑘𝑘
𝑗𝑗=1
 Solution
U1 Optimal cost =
U2 1023€
k
0 2 4 6 8 10 (hr)

Supply
8 Discharge tank level
6
3
4
2
2
0 1
1 2 3 4 5 6 7 8 9 10
0
1 2 3 4 5 6 7 8 9 10

Supply tank level

6

4
Demand
8
2 6

0 4
1 2 3 4 5 6 7 8 9 10 2
0
1 2 3 4 5 6 7 8 9 10
 Solution with terminal constraints
h(10) ≤ 2.5
U1 n(10) ≥ 2.5
U2 Optimal cost = 1644€
k
0 2 4 6 8 10 (hr)

Supply Discharge tank level

8 6
6 4
4
2
2
0
0
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

Supply tank level

4 Demand
3 8
2 6
1 4
0 2
1 2 3 4 5 6 7 8 9 10 0
1 2 3 4 5 6 7 8 9 10
 Continuous time representation
Tasks
U2 2.1 hr
• Tasks may last any
U1 1.5 hr duration
U3 2.7 hr

Time points associated to units • Tasks linked to slots. Slots

ts11 start or stop at any time.
te11 ts12 te12
U1 • Number of time slots have
te22 to be defined previously
U2
ts31 te31 • Smaller number of time
U3
time variables
• More difficult to deal with
Global time points (time events) shared constraints
U1 • Time instants t are new
variables of the scheduling
U2
problem
U3
time • Events tj can take place at
any time. Its number has
t1 t2 t3 tj to be defined previously
 Event representation
Predefined number of time points or slots
How many?
For flowshop problems
t3
t2

Time slots: Tasks must

t1
t3
be assigned to each J1
e b t2

time slot
t1
a c d
J2

General or inmediate
precedence to order
tasks over time
Two main types of problems
Flowshop

Allocation,
sequencing, routing
No recycling or
splitting,mixing

Networks

STN

RTN
 Network problems

1h 10% 2h 90%

1h Reaction1 S3 Separation S4
S1 Heat S2 3h 70% 40% 2h
Reaction2 S5 Reaction 3 S7
60%
30%
S6

STN
 Multiproduct single stage
scheduling

Product 1 Unit 1

Product 2
Unit 2
Product i

…….
……
Product n
Unit L

Task duration L similar units that can

Maximum ending perform the task, but,
Minimum starting
time (Due date) perhaps with different costs
time (Release
or processing times
time) Each of the n products must be
processed in a unit and only in one
 Assigning and sequencing
Assign each product to a unit and compute processing order and
execution time, so that the time constraints are satisfied and the
processing costs are minimized

Product 1
Product 2
Unit 1
Product 3
Unit 2
Product 4
Unit 3
Product 5
Product 6

Assign Sequence
 Allocation MILP
1 if product i is assigned to unit m
y im = 
0 otherwise ri minimum
starting time of
min
y , ts
∑ ∑C
i∈I m∈M
im y im Cost product i
di maximum ending
s.t. ts i ≥ ri Start time ti time of product i

ts i + ∑ pim yim ≤ d i ∀i ∈ I
m∈M
pim processing time
of product i in unit
m
∑y
m∈M
im = 1 ∀i ∈ I Unit assigment Cim cost of
processing product
∑y
i∈I
im p im ≤ max i {d i } − min i {ri } ∀m ∈ M i in unit m
tsi starting time of
pim Total processing product i
m time in a unit m
 Sequencing within every unit

1 If product i precedes product j in unit m

z ij = 
0 Otherwise

1 If product i is assigned to unit m

y im =
0 Otherwise

If product i and product j are assigned to unit m, then i precedes j or j precedes i

1 ≥ z ij + z ji ≥ y im + y jm − 1 ∀i, j ∈ I, i > j, m ∈ M
If product i precedes product j in unit m, then the start time of product j
must be larger than the start time of product i plus task i duration

ts j ≥ ts i + ∑p
m∈M
im y im − M (1 − z ij ) ∀i, j ∈ I, i ≠ j Big-M Constraint

y im = {0,1}, z ij = {0,1}, ts i ≥ 0 MILP problem

 Optimal assignment of chemical products to
batch reactors (single stage multiproduct , 7
products and 3 reactors ).
Minimum Processing Processing Processing
Cost in Cost in Cost in
Product starting Due date time in time in time in
reactor 1 reactor 2 reactor 3
time reactor 1 reactor 2 reactor 3
A 1 8 3 2 4 2 3 2
B 1 10 5 6 5 3 3 2
C 4 7 4 3 5 1 1 1
D 2 9 5 2 7 2 3 2
E 3 7 3 2 6 3 2 3
F 1 7 3 3 5 3 4 4
G 3 8 4 4 6 1 1 1

Find the assignment of

? products to reactors, and
its sequencing, that fulfils
time constraints and
optimize processing costs
 Optimal cost solution
Minimum Processing Processing Processing
Cost in Cost in Cost in
Product starting Due date time in time in time in
reactor 1 reactor 2 reactor 3
time reactor 1 reactor 2 reactor 3
A 1 8 3 2 4 2 3 2
B 1 10 5 6 5 3 3 2
C 4 7 4 3 5 1 1 1
D 2 9 5 2 7 2 3 2
E 3 7 3 2 6 3 2 3
F 1 7 3 3 5 3 4 4
G 3 8 4 4 6 1 1 1

Optimal cost: 22

Reactor 1 F G A B
Reactor 2 E C D
Reactor3
1 2 3 4 5 6 7 8 9

Gantt diagram
 Related problems

min W
y im , W
Different aim: minimize makespan W
ts i + ∑ y im p im ≤ W i∈ I
m Makespan is an upper bound for the
0 ≤ W ≤ Wmax end time of operation of each task

∑y im =1 i∈I Each task i can be performed only

m∈ Fi in a subset Fi of M
y im = 0 m ∉ Fi

Tasks 11 and i2 cannot be performed

yi m + yi m ≤ 1
1 2
i1 , i 2 ∈ N in the same equipment m
y im ∈ {0,1}
 Minimum makespan problem
Minimum Processing Processing Processing
Cost in Cost in Cost in
Product starting Due date time in time in time in
reactor 1 reactor 2 reactor 3
time reactor 1 reactor 2 reactor 3
A 1 8 3 2 4 2 3 2
B 1 10 5 6 5 3 3 2
C 4 7 4 3 5 1 1 1
D 2 9 5 2 7 2 3 2
E 3 7 3 2 6 3 2 3
F 1 7 3 3 5 3 4 4
G 3 8 4 4 6 1 1 1

Optimal makespan: 6 h

Reactor 1 A D G
Reactor 2 F C
Reactor3 B E
1 2 3 4 5 6 7 8 9

Gantt diagram