Hybrid continuous scatter search approach to tardiness related scheduling problems

Abstract

In this thesis, a hybrid approach, which integrates Scatter Search (SS) and a Variable Neighborhood Search (VNS), is presented to attack tardiness related scheduling problems. The aim is to find advanced strategies that can be adapted to the basic SS methodology in order to enhance its diversification and intensification capabilities throughout the scheduling problems. The Hybrid Continuous Scatter Search (HCSS) approach is first implemented on the Single Machine Total Weighted Tardiness (SMTWT) problem to minimize total weighted tardiness. Then the HCSS method is modified to addresses the Parallel Machine Total Tardiness (PMTT) problem, which consists of a set of jobs to be scheduled on a number of parallel processors to minimize total tardiness. The NP-hard nature of both problems renders a challenging area for research. In order to develop a robust hybrid methodology, the key elements of the Scatter Search such as reference set update method, initial solution generation method, solution combination method and as an intensification strategy the hybridized VNS are investigated. The employed solution encoding, diverse solution selection methods, and dynamic solution combination method are unique and introduced first time in this thesis to provide new ideas for Scatter Search era. The proposed HCSS approach yields good quality results with respect to optimal/best-known solutions reported in the literature.