10.3.5 Job Shop Scheduling

Suppose there are n jobs, J₁, J₂,..., J_n to be processed one at a time in non-preemptive fashion. Let the processing time be t₁, t₂,..., t_n and the due dates be d₁, d₂,..., d_n. A schedule for the jobs is a permutation $\pi$ 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 $\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?