An Improved Heuristic for Single Machine Lot Scheduling Problem

Abstract

This work investigates the problem of single machine lot scheduling with the objective of minimizing the total completion time of jobs.Each processing lot is with a uniform capacity and is of identical processing time. Jobs assigned to the same lot are all completed at the end time of the lot. The problem has been investigated in Yang et al. (2017) where they tested the performances of classical scheduling rules including Best Fit Random (BFR), Best Fit Non-decreasing (BFN), Next Fit Non-decreasing (NFN), etc, and showed by experiments that BFN outperforms the other rules. In this paper we extend the work of Yang et al. (2017), and propose an improved BFN algorithm named IBFN, which makes a refined adjustment of job assignment, based on the BFN schedule, to reduce the spare space of each lot as much as possible. Numerical results show that the proposed IBFN algorithm behaves better than BFN in all the experimental instances.