**Next:**10.3.6
Satisfiability**Up:**10.3
Examples of some Intractable Problems**Previous:**10.3.4
Bin Packing

##
10.3.5 Job Shop Scheduling

Suppose there are** ***n*** **jobs**, ***J*_{1},
*J*_{2},..., *J*_{n}** **to be processed one
at a time in non-preemptive fashion. Let the processing time be** ***t*_{1},
*t*_{2},..., *t*_{n}** **and the due dates
be** ***d*_{1},
*d*_{2},..., *d*_{n}**. **A schedule for the
jobs is a permutation
of** **1, 2,..., *n***. **Job *J*_{i}(*i*
= 1,..., *n*)** **will incur a penalty of *p*_{i}(*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?*

eEL,CSA_Dept,IISc,Bangalore