Scheduling jobs on parallel machines applying neural network and heuristic rules

Abstract

In this paper, we investigate the problem of scheduling jobs on identical parallel machines. The jobs are assumed to have sequence dependent setup times independent of the machine. Each job has a processing time, a due date, and a weight for penalizing tardiness. The objective of scheduling is to find a sequence of the jobs which minimizes the sum of weighted tardiness. We propose an extension of the ATCS (Apparent Tardiness Cost with Setups) rule developed by I,ee et al. (1997) which utilizes some look-ahead parameters for calculation the priority index of each job. Scheduling jobs on parallel machines with sequence-dependent set-up times. Technical report. Columbia University; Lee, Y.H., Bhaskaran, K., & Pinedo, M., 1997. A heuristic to minimize the total weighted tardiness with seqence-dependent setups. IIE Transactions, 29, 45-52.) which utilizes some look-ahead parameters for calculating the priority index of each job. The look-ahead parameters were introduced as a tuning mechanism which adjusts the discount rate inside the priority calculation according to the given problem characteristics. To determine the proper values of the look-ahead parameters, Lee identified some measures for describing problem characteristics. They proposed four factors to describe properties of the problem instances,and a heuristic curve-fitting method was used to determine the equations for calculating proper values of the look-ahead parameters. In our approach, an additional factor for measuring the problem characteristics is introduced and we also utilize a neural network to get more accurate values of the look-ahead parameters. Our computational results show that the proposed approach outperforms Lee et al.'s (1997) original ATCS and a simple application of ATCS. (C) 2000 Elsevier Science Ltd. All rights reserved.