No label defined (Q3988451)

The author states a multistep job allocation problem which consists of the decision how \(m\) jobs should be assigned to \(n\) different parallel machines to minimize two criteria. The jobs are devided into \(k\) ordered batches and in each step of the decision jobs of the current batch are allocated. The problem data are described by the job batches, the job processing times, \(t_{i,j}\) (processing time of job \(i\) if this job is assigned to machine \(j\)), and machine release times, \(t_{\text{rel},j}\), at the beginning of the allocation. As objectives for the bicriterial problem, the author uses the total processing time \(E\) (the sum of all job processing times after the allocation) and the makespan \(T\) (the difference between the largest job completion time and the smallest machine release time). It should be mentioned that minimizing \(E\) separately is trivial, whereas minimizing \(T\) separately is already an NP-hard problem. Hence, the bicriterial problem is hard to solve. The author numerically compares four variants of an approach which is motivated by a packing problem. In the packing problem, partially filled bins are packed with `deformable' items (the size of each item depends on the bin in which the item is packed). As objective for the packing problem, the author considers four variants, namely \(E\), \(T\), \(E\cdot T\) and a combination of \(E\) and \(T\). Unfortunately, from the numerical results for 3 test problems (5 job batches, each consists of 7 jobs, and 4 machines), it can not be concluded that there is a significant correlation between the packing variant used and the performance of the heuristic solution.