SINGLE-MACHINE SCHEDULING WITH COUPLED TASK AND REJECTION

We consider the single-machine scheduling with coupled task and rejection, in which each coupled task is either accepted and processed on a single machine or rejected with a certain rejection penalty. Each accepted coupled task Ja is made of two tasks with processing times aa and ba, respectively, and a fixed exactly time interval La between the two tasks is required. The objective is to minimize the makespan of the accepted coupled task and the total penalty of the rejected coupled task. We present 3-approximation algorithm for the cases of aa = La = p and ba = La = p, respectively, and prove that the problems with common ba or common aa is polynomially solvable. Furthermore, when aa = ba = p, we provide a 2-approximation algorithm for La > p and show that the problem with for La & LE; p can be solved in polynomial time.