An Iterative Heuristic Algorithm for Minimizing Total Weighted Tardiness of Unrelated Parallel Batch Processing Machines with Unequal Ready Times

摘要

Unrelated Batch Processing Machines (BPM) can simultaneously process several jobs as a batch, as long as the machine capacity is not exceeded. This type of machine is found in diverse manufacturing and service environments in which machines may have different speeds for different jobs. Specifically, this work was motivated by a practical application observed at an electronics manufacturing and testing facility. The objective is to schedule the batches formed on the machines such that the total weighted tardiness is minimized. Since the problem under study is NP-hard, an iterative heuristic algorithm, based on some dispatching rules, is proposed. This heuristic considers the batching and scheduling problems simultaneously by iteratively assigning jobs to batches and machines that provides the smallest increment in the total weighted tardiness. To verify the effectiveness of the heuristic a set of problem instances were generated combining the number of jobs, job size, spread of the release dates, and tightness of the due dates. Results were compared to a heuristic to form batches using five different dispatching rules to sequence the job. Experimental results indicate that the proposed heuristic is an effective rule for this scheduling problem and outperforms on average the other heuristic.