Next:10.3.6 SatisfiabilityUp:10.3 Examples of some Intractable ProblemsPrevious:10.3.4 Bin Packing

10.3.5 Job Shop Scheduling

Suppose there are n jobsJ1, 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 be d1, d2,..., dn. A schedule for the jobs is a permutation $ \pi$ 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 $ \pi$. 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?