Single Machine Scheduling with a Restricted Weight-Modifying Activity to Minimize the Weighted Makespan

In this paper, we consider the single machine scheduling problem with a restricted Weight-Modifying Activity (WMA) in which the weight of a job is reduced if it is scheduled after such a WMA. We also assume that the starting time of the WMA must fall in a given time interval [Formula: see text]. Our task is to schedule all jobs and the WMA such that the weighted makespan (the maximum weighted completion time) is minimized. We show that a special case with [Formula: see text] can be solved in polynomial time and the general problem and two special cases with [Formula: see text] or [Formula: see text] are binary NP-hard. Furthermore, we propose a pseudo-polynomial dynamic programming algorithm for the above NP-hard problems. Finally, we also provide a fully polynomial time approximation scheme (FPTAS) for the special case with [Formula: see text].