List-Scheduling and Column-Generation for Scheduling of n Job-Groups with Set up Time through m Identical Parallel Machines to Minimize Makespan

Abstract

This paper presents an optimization based heuristic for minimizing makespan on scheduling of n job-groups with q; as the number of identical jobs, p; as the processing time and su; as the setup time required, in job-group i through a set of m identical parallel machines. This heuristic, referred as LSCCG, is based on LS (List-Scheduling) heuristic and CG (Column Generation) which are 'hybrid between the well-known in scheduling problems such as the LPi (Longest Processing Time) heuristic or in packing problems such as _the BFD (Best-Fit Decreasing) heuristic and column generation procedure in a cutting stock problem, respectively. The first algorithm, referred to as LP.TCCG which are hybrid between LPT heuristic. is constructed using the initial pattern and adjusted to a lower bound by ALSP (Adjusted list-scheduling pattern); while the CG. is modi tied to CCG (Continuous column generation) attempting to strengthen makespan bound and collectively generated patterns to minimize a number of machines required. This model is repeatedly looped by LPT, ALSP and CCG to reach an upper bound of minimum makespan. The average performance of this proposed algorithm is considerably better than that of the LPT heuristic. The better algorithm. referred to as BFDCCG. is based on BFD heuristic and CG. As the same princip-le, the BFD heuristic is generated the initial pattern and adjusted to a lower bound by A LSP and then attempted to strengthen makespan bound with a number of available machines by CCG. BFDCCG heuristic is repeatedly looped by BFD. ALSP and CCG to reach an upper bound of minimum makespan. The average performance of this proposed algorithm. BFDCCG heuristic is considerably better than that of the LPTCCG heuristic and computational time also. In set up time case, referred to as LPTsuCCG and BFDsuCCG which are similar to LSCCG, the only difference is in the set up time addition after List-scheduling the initial pattern and sub problem formulation in CCG procedure. As expected, the average performance and computational time of the BFDsuCCG heuristic is considerably better than the LPTsuCCG heuristic.