Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost (Q2174270)

In this paper, scheduling problems with controllable processing times and a common deadline are studied for single and parallel machine environments with parallel identical and uniform machines, respectively. Given are \(n\) jobs \(j=1,\ldots,n\) with release dates \(r(j)\) and deadlines \(d(j)\) saying that job \(j\) has to be completely processed in this interval. Processing of any job can be preempted and resumed later (on the same or on a different machine). In contrast to the classical case, the processing time \(p(j)\) of job \(j\) is not known in advance, but has to be chosen from an interval \([l(j), u(j)]\). Then the value \(x(j)=u(j)-p(j)\) denotes the compression amount of job \(j\) and the objective is to minimize the total compression cost \(\Phi_\Sigma=\sum w(j)x(j)\) or the maximum compression cost \(\Phi_{\max}=\max x(j)/w(j)\). It is shown that problems \(\alpha |r (j) , p(j) = u(j)-x(j), C(j) \le d, pmtn|\Phi_{\max}\) for \(\alpha \in \{1, P, Q\}\) (single machine, identical parallel machines, uniform machines) where the jobs have a common deadline \(d(j)=d\) can be solved in polynomial time. For this, a general methodology is proposed using a special representation of the solution region as a submodular polyhedron intersected with a box.