Minimising makespan on a batch processing machine using heuristics improved by an enumeration scheme. Issue 1 (2nd January 2017)

• Record Type: Journal Article
• Authors: Li, XiaoLin; Li, YuPeng; Wang, Yu
• Is Part Of: International journal of production research. Volume 55:Issue 1(2017)
• Page Start: 176
• Page End: 186
• Publication Date: 2017-01-02
• Subjects: batch scheduling -- heuristics -- makespan -- enumeration scheme -- time complexity; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2016.1200762
• Languages: English
• ISSNs: 0020-7543

Abstract

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.