Examples of some Intractable ProblemsPrevious:10.3.4
10.3.5 Job Shop Scheduling
Suppose there are n jobs, J1,
J2,..., Jn to be processed one
at a time in non-preemptive fashion. Let the processing time be t1,
t2,..., tn and the due dates
d2,..., dn. A schedule for the
jobs is a permutation
of 1, 2,..., n. Job Ji(i
= 1,..., n) will incur a penalty of pi(i
= 1,..., n)if it misses the due-date in the given schedule .
If processed within the due-date, the penalty is taken as zero. The
processing times, due-dates, and penalties are all positive integers. The
penalty of a schedule is the sum of penalties incurred by jobs processed
according to that schedule.
Optimization Problem: Determine the minimum possible penalty for a schedule
and find an (optimal) schedule that achieves the minimum penalty.
Decision Problem: Given a non-negative integer k, does there
exist a schedule with penalty at most k?