کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475405 | 699303 | 2016 | 8 صفحه PDF | دانلود رایگان |
• We minimize the normalized sum of squared workload deviations to balance workload.
• We develop an exact algorithm for the case of three machines.
• We propose an effective subset sum based local search procedure for multiple machines.
• The innovation is to use triples of machines as a neighborhood instead of pairs.
• We optimally solve 98% of the benchmark instances within very short computation time.
The paper on hand addresses the workload balancing problem that asks for an assignment of n independent jobs to m identical parallel machines so that the normalized sum of squared workload deviations (NSSWD-criterion) is minimized. For the special case of m =3 machines we propose an exact algorithm that requires solving a sequence of subset sum problems. This algorithm also builds the core of our local search procedure for solving the general case of m≥3m≥3 machines. The main innovation of our approach compared to existing methods, therefore, consists in using triples of machines as a neighborhood instead of pairs of machines. Results of a comprehensive computational study on the benchmark library established by Ho et al. [10] and Cossari et al. [5] attest to the effectiveness of our approach. In addition, we demonstrate its capability to determine high-quality solutions for further balancing criteria as discussed in Cossari et al. [6].
Journal: Computers & Operations Research - Volume 73, September 2016, Pages 84–91