Chapter VI
Scheduling Models
Prepared by:
Engr. Romano A. Gabrillo
MEngg-MEM
Scheduling Problems
Scheduling problem is a special type of integer
programming problem where assignees are
being assigned to perform tasks.
It involves the following problems:
Production Problems
Transshipment Problems
Production Problems
Production problems involve a single product
which is to be manufactured over a number of
successive time periods to meet prespecified
demands.
The objective is to determine a production
schedule which will meet all future demands at
minimum total cost (which is total production
cost plus total storage cost, as total shipping cost
is presumed fixed).
RAG 2007
Solution to Production Problems
Production problems may be converted into
transportation problems by considering the time
periods during which production can take place as
sources, and the time periods in which units will be
shipped as destinations.
The production capacities are taken to be the supplies.
Therefore, xij denotes the number of units to be
produced. cij is the unit production cost during time
period i plus the cost of storing a unit of product from
time period i until time period j. Since units cannot be
shipped prior to being produced, cij is made
prohibitively large for i > j to force the corresponding
xij to be zero.
RAG 2007
Example No. 1
An industrial firm must plan for each of the four
seasons over the next year. The companys production
capacities and the expected demands (all in units) are as
follows:
Spring Summer Fall Winter
Demand
250
100
400 500
Regular
200
Capacity
Overtime 100
Capacity
300
350
50
100 150
RAG 2007
Regular production costs for the firm are P7.00 per
unit; the unit cost of overtime varies seasonally, being
P8.00 in spring and fall, P9.00 in summer, and P10.00
in winter.
The company has 200 units of inventory on January 1,
but as it plans to discontinue the product at the end of
the year, it wants no inventory after the winter season.
Units produced on regular shifts are not available for
shipment during the season of production; generally,
they are sold during the following season. Those that
are not added to inventory are carried forward at a cost
of P0.70 per unit per season. In contrast, units
produced on overtime shifts must be shipped in the
same season as produced. Determine a production
schedule that meets all demands at minimum total cost.
RAG 2007
Input the Supply and Demand
Sources
Spring
Summer
Destination
Fall
Winter
Dummy
Supply
Regular
(Spring)
200
Regular
(Summer)
300
Regular
(Fall)
350
Initial
Inventory
200
Overtime
(Spring)
100
Overtime
(Summer)
50
Overtime
(Fall)
100
Overtime
(Winter)
150
Demand
250
100
400
500
ui
200
vj
RAG 2007
Input the Costs for Regular Season
Sources
Spring
Summer
Destination
Fall
Winter
Regular
(Spring)
10000
7.00
7.70
8.40
Regular
(Summer)
10000
10000
7.00
7.70
Regular
(Fall)
10000
10000
10000
7.00
Dummy
Supply
200
300
350
Initial
Inventory
200
Overtime
(Spring)
100
Overtime
(Summer)
50
Overtime
(Fall)
100
Overtime
(Winter)
150
Demand
250
100
400
500
ui
200
vj
RAG 2007
Input the Cost for Overtime Capacity
Spring
Summer
Destination
Fall
Winter
Regular
(Spring)
10000
7.00
7.70
8.40
Regular
(Summer)
10000
10000
7.00
7.70
Regular
(Fall)
10000
10000
10000
7.00
Dummy
Sources
ui
200
300
350
Initial
Inventory
200
Overtime
(Spring)
8.00
10000
10000
10000
Overtime
(Summer)
10000
9.00
10000
10000
Overtime
(Fall)
10000
10000
8.00
10000
Overtime
(Winter)
10000
10000
10000
10.00
Demand
Supply
250
100
400
500
100
50
100
150
200
vj
RAG 2007
Input the Cost for Initial Inventory
Sources
Spring
Summer
Destination
Fall
Winter
Regular
(Spring)
10000
7.00
7.70
8.40
Regular
(Summer)
10000
10000
7.00
7.70
Regular
(Fall)
10000
10000
10000
7.00
Initial
Inventory
0.00
0.70
1.40
2.10
Overtime
(Spring)
8.00
10000
10000
10000
Overtime
(Summer)
10000
9.00
10000
10000
Overtime
(Fall)
10000
10000
8.00
10000
Overtime
(Winter)
10000
10000
10000
10.00
Demand
250
100
400
500
Dummy
Supply
ui
200
300
350
200
100
50
100
150
200
vj
RAG 2007
10
Input the Cost for the Dummy
Supply
Sources
Spring
Summer
Fall
Destination
Winter
Dummy
Regular
(Spring)
10000
7.00
7.70
8.40
Regular
(Summer)
10000
10000
7.00
7.70
Regular
(Fall)
10000
10000
10000
7.00
Initial
Inventory
0.00
0.70
1.40
2.10
10000
Overtime
(Spring)
8.00
10000
10000
10000
Overtime
(Summer)
10000
9.00
10000
10000
Overtime
(Fall)
10000
10000
8.00
10000
Overtime
(Winter)
10000
10000
10000
10.00
Demand
250
100
400
500
Supply
ui
200
300
350
200
100
50
100
150
200
vj
Since all units in initial inventory already have been produced, a positive
allocation from initial inventory to the dummy must be avoided. This is done
by assigning a prohibitively large number 10000 as the associated unit cost.
RAG 2007
11
Excel Solver Installation
The Excel Solver is part of the Solver Add-in of
Microsoft Excel which you can find in the Data Menu.
It is first being installed in the computer by clicking the
Office Toolbar (for Office 2007) and click Excel
Options.
On the left side of the Options Dialog-Box, select AddIns. On the Add-Ins name, search for Solver Add-in
and click Go. The Excel Solver will now be installed
on your computer.
12
Solve Using Excel Solver
Input the Transportation Tableau on the
Spreadsheet.
Spring
Summer Fall
Winter
Dummy
Supply
R-Spring
10000
7
7.7
8.4
0
200
R-Summer
10000
10000
7
7.7
0
300
R-Fall
10000
10000
10000
7
0
350
Initial Inventory
0
0.7
1.4
2.1
10000
200
O-Spring
8
10000
10000
10000
0
100
O-Summer
10000
9
10000
10000
0
50
O-Fall
10000
10000
8
10000
0
100
O-Winter
10000
10000
10000
10
0
150
Demand
250
100
400
500
200
RAG 2007
13
Input Another Cell Range Just Below It
Spring
R-Spring
R-Summer
R-Fall
Initial Inventory
O-Spring
O-Summer
O-Fall
O-Winter
Total
Summer
0
0
0
0
0
0
0
0
0
Fall
0
0
0
0
0
0
0
0
0
Winter
0
0
0
0
0
0
0
0
0
Dummy
0
0
0
0
0
0
0
0
0
Total
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
The Row and Column Total must have the
formula for the sum of the respective row and
column.
RAG 2007
14
Create the Cell for the Costs (z)
Create a cell just below the new range of cells
with the formula as the sumproduct of range of
cells above with the range of cells below
excluding the row and column for the row total,
column total, demand and supply.
Example:
=SUMPRODUCT(B2:F9,B14:F21)
RAG 2007
15
The Excel Solver
On the Data Menu, Choose Solver and the
Solver Parameters Dialog Box will appear:
RAG 2007
16
Input Parameters on the Solver
Dialog Box
Set the Target Cell as the Cell corresponding for the
cost (z).
Set the Equal to Option to Minimum, as with the
minimization program of the transportation tableau.
Set the Range of cells that you have created below the
transportation tableau as the range of cells in the By
Changing Cells Option.
Add the Constraints on the Subject by the Constraints
Option by setting the Row Total equal to total Supply
and the Column Total equal to the Demand Supply.
Click Ok if done.
RAG 2007
17
Getting the Optimal Solution
Click the Options Button and the Solver
Options Dialog Box will appear.
On the Solver Options Dialog Box, select
Assume Linear and Assume Nonnegative
Checkboxes. Click Ok and you will be moved
back the Solver Dialog Box.
Click Solve to get the optimal solution.
The values in the Range of Cells below are the
optimal values of the variables and costs z is the
optimal solution to the problem.
RAG 2007
18
Final Answer
Spring
R-Spring
R-Summer
R-Fall
Initial Inventory
O-Spring
O-Summer
O-Fall
O-Winter
Total
costs
Summer Fall
0
100
0
0
0
0
200
0
50
0
0
0
0
0
0
0
250
100
Winter
Dummy Total
0
100
0
300
0
0
0
350
0
0
0
0
0
0
50
0
0
50
100
0
0
0
50
100
400
500
200
200
300
350
200
100
50
100
150
7790
RAG 2007
19
Transshipment Problems
A transshipment problem, like a transportation
problem, involves sources, having supplies, and
destinations, having demands. In addition, it also
involves junctions, through which goods can be
shipped.
Unit shipping costs are given between all directly
accessible locations, and the objective is to develop a
transportation schedule that will meet all demands at
minimum total cost.
RAG 2007
20
Solution to Transshipment Problems
Transshipmet problems may be converted into
transportation problems by making every junction both
a source and a destination. Each junction is assigned a
supply equal to its original supply (or zero, if the
junction did not originally coincide with a source) plus
the total number of units in the system, same thing with
the demand. These assignments allow for the
possibility that all units may pass through a given
junction.
The cost of transporting 1 unit from a junction
(considered as a source) to itself (considered as a
destination) is zero. Those units that do not pass
through a junction under the optimal schedule will
appear as allocations from
the junction to itself.
RAG 2007
21
Example No. 2
A corporation must transport 70 units of a product
from location 1 to locations 2 and 3, in the amounts of
45 and 25 units, respectively. Air freight charges cij (in
dollars per unit) between locations served by the air
carrier are given below where dotted lines signify that
service is not available. Determine a shipping schedule
that allocates the required number of goods to each
destination at a minimum total freight cost. No
shipment need be flown directly; shipments through
intermediate points are allowed.
RAG 2007
22
38
56
34
38
27
56
27
19
34
19
Table 2
-45
2
$38
+70
$34
$27
$27
$38
$56
1
$56
$34
$19
$19
4
RAG 2007
-25
Figure 2
23
Create the Transportation Tableau
Location 4 is a pure junction.
Locations 2 and 3 serve as both destinations and
junctions.
Location 1 serves both as a source and a junction.
Therefore, we have 1, 2, 3, and 4 as the sources and 1,
2, 3, and 4 as destinations but we delete 1 as a
destination since it could never be optimal to ship
goods from location 1 and have them return as some
later time, only to be shipped out again, the problem
can be simplified by not allowing shipments to location
1, thereby restricting it to being solely a source.
RAG 2007
24
Solution Using Excel Solver
1
2
3
4
2
38
0
27
10000
115
3
56
27
0
19
95
1
2
3
4
Total
2
45
70
0
0
115
3
0
0
70
25
95
Costs
3035
Demand
RAG 2007
4 Supply
34
70
10000
70
19
70
0
70
70
4 Total
25
0
0
45
70
70
70
70
70
25
Assignment Problems
Assignment problems involve scheduling
workers to jobs on one-to-one basis (more
generally, they involve permutations of a set of
objects).
The objective is to schedule every worker to a
job so that all jobs are completed in the
minimum total time (or, to find the permutation
that has the greatest total value).
RAG 2007
26
Solution to Assignment Problems
Assignment problems can be converted into
transportation problems by considering the
workers as sources and the jobs as destinations,
where all supplies and demands are equal to 1.
A solution procedure more efficient than the
general transportation algorithm is the
Hungarian Method (which will be discussed
later).
RAG 2007
27
Example No. 3
For the Figure below, determine a shipping
schedule that meets all demands at a minimum
$8
total cost.
$3
1
+15
$4
+95
$3
$2
$4
+70
-30
$7
RAG 2007
-30
$2
-45
28
Solution
Locations 1 and 2 are sources.
Locations 5 and 6 are destinations
Location is both a source and a junction.
Location 4 serves both as a destination and a
junction.
Because the total supply is 180 units but total
demand is only 105, location 7 is created as a
dummy destination.
RAG 2007
29
Set up the Transportation Tableau
1
2
3
4
demand
3
3
2
0
10000
180
4
10000
7
3
0
210
5
8
10000
4
10000
30
6 dummy 7 supply
10000
0
95
10000
0
70
4
0
195
2
0
180
45
75
6 dummy 7 total
1
2
3
4
0
0
0
0
total
costs
RAG 2007
30
Solve Using Excel Solver
1
2
3
4
3
3
2
0
10000
180
4
10000
7
3
0
210
5
8
10000
4
10000
30
1
2
3
4
total
3
20
70
90
0
180
4
0
0
30
180
210
5
0
0
30
0
30
costs
590
demand
RAG 2007
6 dummy 7 supply
10000
0
95
10000
0
70
4
0
195
2
0
180
45
75
6 dummy 7 total
0
75
0
0
45
0
0
0
45
75
95
70
195
180
31
Hungarian Method
Step 1
In each row of the Hungarian Tableau, locate the smallest
element and subtract it from every element in that row. Repeat
this of each column (the column minimum is determined after
the row subtractions). The revised cost matrix will have at least
one zero in every row and column.
Step 2
Determine whether there exists feasible assignment involving
only zero costs in the revised cost matrix. In other words, find if
the revised matrix has n zero entries no two of which are in the
same row or column. If such an assignment exists, it is optimal.
If no such exists, go to Step 3.
RAG 2007
32
Hungarian Method
Step 3
Cover all zeroes in the revised cost matrix with as few
horizontal and vertical lines as possible. Each
horizontal line must pass through an entire row, each
vertical line must pass through an entire column; the
total number of lines in this minimal covering will be
smaller than n. Locate the smallest number in the cost
matrix not covered by a line. Subtract this number
from every element not covered by a line and add it to
every element covered by two lines.
Step 4
Return to Step 2
RAG 2007
33
Hungarian Tableau
The Hungarian method, uses only the cost matrix,
as input:
Jobs
Workers
1
2
3
...
n
1
c11
c 21
c31
...
cn1
2
c12
c 22
c32
...
cn2
3
c13
c 23
c33
...
cn3
RAG 2007
...
...
...
...
...
...
n
c1n
c 2n
c3n
...
cnn
34
Example No. 4
A 400-meter medley relay involves four different
swims, who successively swim 100 meters of the
backstroke, breaststroke, butterfly, and freestyle. A
coach has six very fast swimmers whose expected time
(in seconds) in the individual events are given below:
Event 1
Event 2
(Backstroke0 (breaststroke)
Swimmer 1
Swimmer 2
Swimmer 3
Swimmer 4
Swimmer 5
Swimmer 6
65
67
68
67
71
69
73
70
72
75
69
71
RAG 2007
Event 3
(butterfly)
Event 4
(freestyle)
63
65
69
70
75
66
57
58
55
59
57
59
35
Solution Using the Hungarian
Method
How should the coach assign swimmers to the
relay so as to minimize the sum of their times?
Solution: Set the Hungarian Tableau
Swimmer 1
Swimmer 2
Swimmer 3
Swimmer 4
Swimmer 5
Swimmer 6
1
65
67
68
67
71
69
2
73
70
72
75
69
71
Events
3
63
65
69
70
75
66
Tableau
RAG 20074A
4
57
58
55
59
57
59
5
0
0
0
0
0
0
6
0
0
0
0
0
0
36
Step 1 of the Hungarian Method
Subtracting 0 from every row of Tableau 4a and
then subtracting 65, 69, 55, 0, and 0 from the
columns 1 through 6, respectively generates
tableau 4b below:
Swimmer 1
Swimmer 2
Swimmer 3
Swimmer 4
Swimmer 5
Swimmer 6
1
0
2
3
2
6
4
2
4
1
3
6
0
2
Events
3
0
2
6
7
12
3
Tableau
RAG 20074B
4
2
3
0
4
2
4
5
0
0
0
0
0
0
6
0
0
0
0
0
0
37
Step 2 of the Hungarian Method
The smallest uncovered element is 1, subtract 1
from every uncovered element and add 1 to
every element covered by 2 lines.
Swimmer 1
Swimmer 2
Swimmer 3
Swimmer 4
Swimmer 5
Swimmer 6
1
0
1
3
1
6
3
2
4
0
3
5
0
1
Events
3
0
1
6
6
12
2
Tableau
RAG 20074C
4
2
2
0
3
2
3
5
1
0
1
0
1
0
6
1
0
1
0
1
0
38
Step 3 and 4 of the Hungarian
Method
Tableau 4c also does not contain a feasible zerocost assignment. Repeating step 3 of the
Hungarian method, we determine 1 is again the
smallest uncovered element as in Tableau 4d:
Swimmer 1
Swimmer 2
Swimmer 3
Swimmer 4
Swimmer 5
Swimmer 6
1
0
0
3
0
5
2
2
5
0
4
5
0
1
Events
3
0
0
6
5
11
1
Tableau
RAG 20074D
4
2
1
0
2
1
2
5
2
0
2
0
1
0
6
2
0
2
0
1
0
39
Optimal Value
Tableau 4d which does contain a feasible zero-cost
assignment, as indicated thus, the optimal allocation is
swimmer 1 to event 1 (backstroke), swimmer 2 to event
3 (butterfly), swimmer 3 to event 4 (freestyle), and
swimmer 5 to event 2 (breaststroke); swimmers 4 and 6
are not entered in the medley.
The minimum total time (in seconds) is calculated from
Tableau 4a.
z = c11 + c23 + c34 + c52 = 65+65+55+69= 254s
RAG 2007
40
Schedule of Final Exam
December 6, 2013
Coverage: Chapters 5-6
Friday, 3-5pm
Bring your own laptop with Excel Solver!
41
End of Module
Thank you very much for listening!
42