Content area
Batch processing machines are commonly used in manufacturing industries such as wafer fabrication, metal working, burn-in ovens and testing electrical circuits. Batch processing machines can process several jobs simultaneously. Due to growing competition, many manufacturers employ batch processing machines in order to reduce setup and overall processing (cycle) times. Batch processing machines are expensive. They should be utilized to the greatest extent possible to improve their benefit-to-cost ratio. The utilization of the batch processing machines can be improved by minimizing the makespan or the completion time of the last batch of jobs.
The problem under study considers a set of batch processing machines in parallel commonly used to test Printed Circuit Boards (PCBs). The batch processing machine can process a batch of jobs as long the total size of all the jobs in the batch does not exceed the machine capacity. The processing time of the job and its size is given. The processing time of the batch is equal to the longest processing job in the batch. The objective is to minimize the makespan. A special case of the problem under study is NP-hard. Consequently, the problem under study is NP-hard. Exact procedures may require long processing times. (Abstract shortened by UMI.)