

Operations
Research (MTH601)
270
10000
10
20
10
20000
10
20
20
30000
30
20
20
40000
40
30
30
50000
40
30
40
Segment
X: Miscellaneous
Lectures
4445
270
Operations
Research (MTH601)
271
SEQUENCING
INTRODUCTION
A
series, in which a few jobs
or tasks are to be performed
following an order, is
called
sequencing.
In such a situation, the
effectiveness measure (time,
cost, distance etc.,) is a
function of
the
order or sequence of performing a
series of jobs. Problems of
sequencing can be classified
into
two
major groups.
In
the first type of problem,
we have n
jobs to
perform each of which
requires processing on
some
or all m
different
machines. If we analyze the
number of sequences, it runs to
(n!)m possible
sequences
and only a few of them
are technologically feasible,
i.e., those which satisfy
the constraints
on
the order in which each
task has to be processed
through m
machines.
In
the second type of problem,
we have a situation with a
number of machines and a
series
jobs
to perform. Once a job is
finished, we have to take a
decision on the next job to
be started.
Practically
both types of problems seem
to be intrinsically difficult and
now we know solutions
only
for some special cases of
the first type of problem.
For the second type of
problems, it appears
that
a few empirical rules have
been obtained to arrive at
the solution and
mathematical theory has
to
be
explored.
PROCESSING
n
JOBS
THROUGH TWO
MACHINES
The
sequencing problem with n
jobs through two machines
can be solved easily.
S.M.
Johnson
has developed solution
procedure. The problem can
be stated as follows.
Only
two machines are involved,
A
and
B.
1.
Each
job is processed in the
order AB.
2.
The
exact or expected processing
times A1,
A2,
..., An,
B1,
B2,
..., Bn are
known.
3.
A
decision has to be arrived to
find the minimum elapsed
time from the start of
the first job to
the
completion of the last job.
It has been established that
the sequence that minimizes
the elapsed
time
are the same for
both machines. The algorithm
for solving the problem is
as follows and due to
S.M.
Johnson.
Select
the smallest processing time
occurring in the list,
A1,
..., An,
B1,
... , Bn.
If there
1.
is
a tie, break the tie
arbitrarily.
If
the minimum processing time
is Ai,
do the ith
job first. If it is Bj do
the jth
job last.
2.
This
decision is applicable to both
machines A
and
B.
Having
selected a job to be ordered,
there are now n1, jobs
left to be ordered.
Apply
3.
the
steps 1 and 2 to the reduced
set of processing times
obtained by deleting the
two
machine
processing times corresponding to
the job that is already
assigned.
Continue
in this manner until all
jobs have been ordered.
The resulting ordering
will
4.
minimize
the elapsed time, T.
THE
TRAVELLING SALESMAN
PROMLEM
In
this type of problem, we
have to select a route by a
salesman that will minimize
the total
distance
traveled in visiting n
cities and
returning to the starting
point. Another example is
that if n
271
Operations
Research (MTH601)
272
products
are to be made in some order
on a continuing basis, and
the set up cost for
each
depends
on the preceding product
made, we want to find cost
for each depends on the
preceding
products
that will minimize the
total set up cost when
the product Ai is
followed by Aj.
The set up costs
are
represented in square matrix,
while the leading diagonal
blank, indicating no set up
cost when
changing
a product to itself. In traveling
salesman problem, we cannot
choose the element along
the
diagonal
and this can be avoided by
filling the diagonal with
infinitely large elements.
Another
constraint
we have to work with is that
having started from a
station Ai say,
we do not want to go to
the
same station again until we
have moved to all other
stations.
INTEGER
PROGRAMMING
INTRODUCTION
In
linear programming problem,
the decision variables
represent men, machines,
vehicles,
number
of items to be produced etc.
These variables make sense
only if they have integer
values in
the
final solution to the linear
programming problem. This is
the problem faced in real
life practice. For
example,
if we get a solution to a problem
when we decide on the number
of chairs and tables
produced
per day in a furniture
industry. As 2.53 chairs and
3.82 tables, it is meaningless
because of
noninteger
solution. Hence a new
procedure has been developed
in this direction for the
case of
linear
programming problems subjected to
the additional restriction
that the decision variables
must
have
integer values.
For
solving this type of integer
linear programming problems,
the usual technique is to
apply
the
simplex method ignoring the
integer restriction and then
rounding off the noninteger
values to
integers
in the resulting solution.
There are some pitfalls in
this approach. One is that
it is difficult to
see
in which way the rounding
off should is rounded off
successfully, there is no guarantee
that this
roundedoff
solution will be the optimal
integer solution. In fact it
may be far from optimal in
terms of
the
value of the objective
function.
This
can be illustrated by the
following problem.
Maximize
Z
= 2x
+ 10y
x
+ 10y
< 20
Subject
to
<2
x
and
x
and
y
are
nonnegative integers.
Since
this problem involves only
two variables, a graphical
solution can be easily
obtained which is
given
below.
The
graphical solution is used to
find the optimal integer
solution or optimal
noninteger
solution.
The optimal noninteger
solution should be x
= 2 and
y
= 9/5 with
Z*
= 22. If
the simple
procedure
is adopted, then the
variable with the
noninteger value y
= 9/5 in
rounded off in the
feasible
direction to y
= 1. Then
the resulting integer
solution is x
= 2, y
= 1 and
Z*
= 14. But
this is far
from
the optimal solution,
(x, y) = (0, 2)
where Z*
= 20
Therefore
an efficient solution procedure
for obtaining an optimal
solution to integer
programming
problems is necessary. Some
progress has been made in
recent years in
developing
algorithms
(solution procedures) for
integer programming
problems.
272
Table of Contents:

