As a prototype, consider the problem of sequencing
a set of n jobs through a single machine that can
work on only one job at a time. Once a job is started,
it must be completed without preemption. The time required
to process job j once the machine begins to work on
it is p(j) for j = 1,...,n. The
associated cost c(j,t) is a function
of its completion time t and can take a variety of
forms, the simplest being
c(j,t) = a(j)t
where a(j)
is the cost per unit time for job j. This form
admits a very simple solution when the objective is to minimize
the total completion cost of all the jobs. The optimum
is obtained by computing the ratio p(j)/a(j)
for each job and then sequencing them in order of increasing
values of this ratio. The
job with the smallest ratio is processed first, the job with next smallest
ratio is processed second, and so on until all jobs are completed. Ties
may be broken arbitrarily.
A much more
difficult problem results when each job j has a due
date b(j). The
cost of a job is zero if it is completed before its due date but increases linearly
if it is tardy.
The goal of the optimization is to determine the sequence
that has the smallest total cost. The table gives
the relevant parameters for a 4-job instance.
There are 4!
= 24 possible solutions. For the solution (3, 1, 2, 4),
the completion times are 7, 12, 21 and 31 respectively. Jobs
3 and 1 are completed before their due date so no cost is incurred. Job
2 is 11 days late resulting in a cost of $440 and job 4 is
14 days late resulting in a cost of $420. The total cost
is therefore $860. |
