Two parallel machine sequencing problems involving controllable job processing times (Q1310019)

The authors consider a problem of scheduling \(n\) single-operation jobs on \(m\) non-identical machines. It is assumed that processing time of a job \(j\) by a machine \(i\) is controllable. The cost of performing a job is a linear function of its processing time. The scheduling cost to be minimized is: (A) the total processing cost plus total flow time, (B) the total processing cost plus total weighted earliness and weighted tardiness. For a single machine case \((m=1)\) the problem (A) was considered by \textit{R. G. Vickson} [AIIE Trans. 12, 258-262 (1980)], and the problem (B) was considered by \textit{S. S. Panwalkar} and \textit{R. Rajagopalan} [Eur. J. Oper. Res. 59, No. 2, 298-302 (1992; Zbl 0760.90058)]. The aim of the paper is to extend these results to multiple machines. Each problem is reduced to a transportation problem that can be solved by a polynomial time algorithm.