####
F.C. van Lookeren Campagne
*
Methoden voor paarsgewijze taaktoewijzing.
*

Literature survey,
Report 93.3.LT.4176, Transport Technology, Logistic Engineering.

This report investigates methods to assign couples of jobs to servers.

Couples assignment is a special case of the classic assignment problem,
dedicated to problems where:
- short jobs arise frequently;
- different stages in the jobs can be distinguished, or

the jobs can be split in two groups;
- resettimes are sequence dependant.

Couples assignment is first modelled as a 0,1-problem, minimising the total
costs of the assignment and subjected to the following restrictions:
- Each server is used exactly once in the first assignment;
- Each job is done exactly once after both assignments;
- If a job is assigned in the first round it must have exactly one successor;
- If a job is not assigned in the first round it must have no successors.

In order to use efficient linear programming techniques this 0,1-problem is
transformed to a minimum cost flow problem, which garantees an integer solution
when integer data are used. Therefor restriction 2 is replaced by the following
two:
- Every job is done at most once in the first assignment;
- Every job is done at most once in the second assignment.

Replacing restriction 2 by restriction 2^{a} and 2^{b} creates
the possibility of assigning a certain job twice. The following three techniques
can be used to solve this problem:
- Branch-and-bound techniques: The job assigned twice is forced in the first
assignment or in the second assignment. Then a bound can be found using
the e-Relaxation
Algorithm.
- Using price-rises: The double assigned job is made less "favourable" by a
rising its prices, after which the
e-Relaxation Algorithm can
be used again.
- The minimum cost flow problem is abandoned by adding a restriction which
explicitly forbids to assign a job twice.

Reports on Logistic Engineering (in Dutch)

Modified: 2000.12.08;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.