Abstract:

We study unrelated parallel-machine scheduling problems with deteriorating maintenance activities and job rejection. Each machine has at most one deteriorating maintenance activity throughout the scheduling horizon. The duration of the maintenance activity increases linearly with its starting time. Each job is either processed and it incurs a production cost, or is rejected with a penalty cost. The objective is to find the position of the maintenance activity of each machine and the sequence of the accepted jobs such that the scheduling cost of all accepted jobs plus the total cost of rejecting and processing jobs is minimized. When the scheduling cost is the makespan, we provide an approximation algorithm with worst-case ratio of 2. When the scheduling costs are the total completion time, the total machine load and the total absolute deviation of completion times, we show that the three versions of the scheduling problem can be optimally solved in polynomial time.

Key words: scheduling, unrelated machine, deteriorating maintenance activity, approximation algorithm