Approximation schemes for scheduling on uniformly related and identical parallel machines (Q1879359)

The article treats a scheduling problem with \(n\) jobs \((i,\) processing times (with speed 1) \(pi)\) on \(m\) uniformly related parallel machines, i.e., each machine \(j\) has an assigned speed \((sj)\) and the processing times of the jobs are inversely related to this machine-speed \((pij=pi/sj)\). The objective function is stated in a very general form, s.t. Minimal- maximum- and Minimal-Sum-functions can be treated. Therefore most of the objective functions lead to NP-hard problems. Based on this fact, the authors try to define a set of efficient schedules (which have a chance of being optimal), and formulate an approximation scheme producing a solution whose objective function value is within a certain bound to the (unknown) optimal solution. The main instrument for contructing the approximation is rounding the data to a level which is required by the accuracy of the approximative solution (nearer to the optimum means dealing with larger data and increasing the computational effort).