Scheduling jobs on parallel machines with setup times and ready times

In this research we are interested in scheduling jobs with ready times on identical parallel machines with sequence dependent setups. Our objective is to minimize the total weighted tardiness. As this problem is NP-Hard, we develop a heuristic to solve this problem in reasonable time. Our approach is an extension of the apparent tardiness cost with setups (ATCS) approach by [Lee, Y. H., Pinedo, M. (1997). Scheduling jobs on parallel machines with sequence dependent setup times. European Journal of Operational Research, 100, 464-474.) to allow non-ready jobs to be scheduled - meaning we allow a machine to remain idle for a high priority job arriving at a later time. To determine the scaling parameters for our composite dispatching rule (called ATCSR), we first develop a 'grid approach' that considers multiple values for the scaling parameters, generates multiple schedules, and chooses the best schedule for the solution. This experimentation was then used to develop regression equations to predict the values of the scaling parameters that would yield the highest quality solution. The grid and regression versions of ATCSR provide better performance than grid and empirically based formula versions of ATCS, BATCS, and X-RM which are the prominent algorithms in the literature. (C) 2007 Elsevier Ltd. All rights reserved.