A Hybrid of List-Scheduling and ColumnGeneration for Scheduling of n JobGroups through m Identical Parallel Machines with Minimum Makespan

Abstract

This paper presents an optimization based heuristic for minimizing makespan on scheduling of n job-gr:oups with q; as the number of identical jobs and p, as the processing time, included any 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 LPT (Longest Processing Time) heuristic or IP (Integer Programming) heuristic and column generation procedure in cutting stock problem, respectively. The tirst model. referred as LPTCCG which are hybrid between LPT heuristic, is constructed the initial pattern and adjusted to a lower bound by ALPTP (Adjusted LPT Pattern); while the second method. CG. is modi tied to CCG (Continuous Column Generation) attempting to strengthen makespan bound an.d collectively generated patterns to minimize a number of machines required. This model is repeatedly looped by LPT, ALPTP and CCC to reach an upper bound of minimum makespan. The average performance of this proposed is considerably better than that of LPT heuristic in case of nlm ratio less than 2.5. The Better model, referred as IPCCG, is based on IP (Integer Programming) heuristic by LINGO 6.0 software and CG. As the same. IP heuristic is generated the initial pattern. which is interrupted at 200.000 iterations and adjusted to a lower bound by AIPP (Adjusted IP Pattern) and then attempted to strengthen makespan bound with a number of available machines by CCC. JPCCC heuristic is repeatedly looped by JP Heuristic, AJPP and CCC to reach an-upper bound of minimum makespan. The average performance of this proposed, IPCCG heuristic is considerably better than that of LPTCCG heuristic.