70
3. A Procedure for Solving the Optimal Expansion
Problem
is uniquely determined by x. A particularly important feature of the branch
and bound method is that an optimal solution to a problem can be obtained
with less than complete enumeration of all the possible solutions.
Three typical examples of combinatorial problems that have been solved
by BBA's (as well as by other methods, of course) are the following.
The Traveling Salesman Problem
The problem is to assign values of 0 or 1 to variables
, where x%j is 1 if
the salesman travels from city i to city j and 0 otherwise. The constraints
in the problem are that the salesman must start at a particular city, visit
each of the other cities only once, and return to the original city. Some
cost (here distance) cy is associated with traveling from city i to city j, and
the objective function is to
Minimize the total cost of the trips to each city
subject to
where
/(
χ
) = ΣΣ
c i&u
=
Σ °*
Τχ
*
^ > Xij — 1
^ > Xij — 1
Ci^ — \j^ij } · · · j C%n\
Xi^* — ^J^ij · . · . ,
The Machine Job-Shop Scheduling Problem
The problem is to assign integer values to variables χ^ , where x^ is the
starting time of job i on machine j; j = 1, .. . , n. The constraints in the
problem are that a job cannot be processed on machine η before it has been
completed on machine (η — 1), and it cannot be processed on machine
(η — 1) before it has been completed on machine (n — 2), and so forth.
Given the time Uj that it takes to complete the work of job i on machine j,
the problem is to schedule the jobs on each machine so that the total time
for the completion of all the jobs is a minimum. The objective function is
/(x) = max(^n + tin)
i
Because # tn + U n is the time at which job i is completed on machine n, the
maximum of these numbers is the time at which the latest job is completed.
It is that time which is to be minimized.
3. A Procedure for Solving the Optimal Expansion
Problem
is uniquely determined by x. A particularly important feature of the branch
and bound method is that an optimal solution to a problem can be obtained
with less than complete enumeration of all the possible solutions.
Three typical examples of combinatorial problems that have been solved
by BBA's (as well as by other methods, of course) are the following.
The Traveling Salesman Problem
The problem is to assign values of 0 or 1 to variables
, where x%j is 1 if
the salesman travels from city i to city j and 0 otherwise. The constraints
in the problem are that the salesman must start at a particular city, visit
each of the other cities only once, and return to the original city. Some
cost (here distance) cy is associated with traveling from city i to city j, and
the objective function is to
Minimize the total cost of the trips to each city
subject to
where
/(
χ
) = ΣΣ
c i&u
=
Σ °*
Τχ
*
^ > Xij — 1
^ > Xij — 1
Ci^ — \j^ij } · · · j C%n\
Xi^* — ^J^ij · . · . ,
The Machine Job-Shop Scheduling Problem
The problem is to assign integer values to variables χ^ , where x^ is the
starting time of job i on machine j; j = 1, .. . , n. The constraints in the
problem are that a job cannot be processed on machine η before it has been
completed on machine (η — 1), and it cannot be processed on machine
(η — 1) before it has been completed on machine (n — 2), and so forth.
Given the time Uj that it takes to complete the work of job i on machine j,
the problem is to schedule the jobs on each machine so that the total time
for the completion of all the jobs is a minimum. The objective function is
/(x) = max(^n + tin)
i
Because # tn + U n is the time at which job i is completed on machine n, the
maximum of these numbers is the time at which the latest job is completed.
It is that time which is to be minimized.