Job release scheduling problem: Complexity and an approximation algorithm

We consider the problem of releasing multiple types of jobs to a facility over a fixed period. In the problem, each type of job has its own demand for the period and the daily capacity of the facility can fluctuate. The variability of each type is defined as the total absolute deviation between the number of jobs of the corresponding type released on consecutive days. The objective is to minimize the total variability over all types. We show that the problem is strongly NP-hard. In addition, we develop an approximation algorithm and analyze its approximability according to the level of fluctuation of the daily capacity.