Minimising makespan on a batch processing machine using heuristics improved by an enumeration scheme

Abstract

Batch processing machines can process several job simultaneously and are encountered in many manufacturing environments. Jobs in a batch are processed together and have the same start and end processing time. Since jobs are non-identical in job sizes and job processing times, they should be reasonably scheduled to improve the machine utilisation and processing efficiency. Two well-known heuristics, first fit longest processing time and best fit longest processing time (BFLPT), are improved in this study by considering identical job sizes and then BFLPT is further improved by an enumeration scheme proposed. Computational experiments are conducted to evaluate the performance of the improvement and the results are compared with the existing heuristics.

Keywords:

• batch scheduling
• heuristics
• makespan
• enumeration scheme
• time complexity