Single machine scheduling with unequal release date using neuro-dominance rule

Çakar T.

Journal of Intelligent Manufacturing, vol.22, no.4, pp.481-490, 2011 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 22 Issue: 4
  • Publication Date: 2011
  • Doi Number: 10.1007/s10845-009-0309-3
  • Journal Name: Journal of Intelligent Manufacturing
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.481-490
  • Keywords: Neuro-dominance rule, Single machine scheduling, Total weighted tardiness, Unequal release date
  • Istanbul Gelisim University Affiliated: No


A neuro-dominance rule (NDR) for single machine total weighted tardiness problem with unequal release date is presented by the author. To obtain the NDR, backpropagation artificial neural network (BPANN) has been trained using 10,000 data and also tested using 10,000 another data. Inputs of the trained BPANN are starting date of the first job (t), processing times (pi and p j), due dates (di and dj), weights of the jobs (wi and wj) and ri and rj release dates of the jobs. Output of the BPANN is a decision of which job should precede. Training set and test set have been obtained using Adjusted Pairwise Interchange method. The proposed NDR provides a sufficient condition for local optimality. It has been proved that if any sequence violates the NDR then violating jobs are switched according to the totalweighted tardiness criterion. The proposedNDRis compared to a number of competing heuristics (ATC, COVERT, EDD, SPT, LPT, WDD, WSPT, WPD, CR, FCFS) and meta heuristics (simulated annealing and genetic algorithms) for a set of randomly generated problems. The problem sizes have been taken as 50, 70, 100. NDR is applied 270,000 randomly generated problems. Computational results indicate that the NDR dominates the heuristics and meta heuristics in all runs. Therefore, the NDR can improve the upper and lower bounding schemes. © Springer Science+Business Media, LLC 2009.