An approximation algorithm for the \(m\)-machine permutation flow shop scheduling problem with controllable processing times (Q1310020)

The \(m\)-machine permutation flow shop scheduling problem in which job processing times are decision variables is considered. For every job \(j\) and every machine \(i\) there are given three non-negative numbers \(a_{ij}\), \(u_{ij}\) \((u_{ij}\leq a_{ij})\) and \(c_{ij}\). The processing time of job \(j\) on machine \(i\) is equal to \(a_{ij}- x_{ij}\), where \(0\leq x_{ij}\leq u_{ij}\) is the decision variable. The aim is to find such \(x_{ij}\) \((1\leq j\leq n,\;1\leq i\leq m)\) and a permutation \(\pi\) (which defines the job processing order) that minimize the objective function \(C_{\max}(x,\pi)+ \sum^ m_{i=1} \sum^ n_{j=1} c_{ij} x_{ij}\). Here \(C_{\max}\) is the maximum completion time (makespan). This problem is known to be NP-hard even for \(m=2\) and identical \(c_{ij}\). An approximation algorithm with a worst-case performance ratio equal to 3/2 for \(m=2\) is known as well. In the paper an approximation algorithm is suggested. The worst-case performance ratio of the algorithm is equal to 4/3 for \(m=2\) and does not exceed \((\rho+ \sqrt{\rho(m- 1)})/2+ 1/4+ O(1/\sqrt{\rho m})\) for \(m\geq 2\). Here \(\rho\) is the worst-case performance ratio of an approximate algorithm, which is used for solving the usual (for some fixed \(x\)) \(m\)- machine permutation flow shop scheduling problem. The first bound is tight and the second bound is tight as well for \(\rho=1\).