A new neuro-dominance rule for single-machine tardiness problem with double due date

Abstract

In this study, the single-machine total weighted tardiness scheduling problem with double due date has been addressed. The neuro-dominance rule (NDR-D) is proposed to decrease the total weighted tardiness (TWT) for the double due date. To obtain NDR-D, a back-propagation artificial neural network was trained using 12,000 data items and tested using another 15,000 items. The adjusted pairwise interchange method was used to prepare training and test data of the neural network. It was proved that if there is any sequence violating the proposed NDR-D then, according to the TWT criterion, these violating jobs are switched. The proposed NDR was compared with a number of generated heuristics. However, all of the used heuristics were generated for double due date based on using the original heuristic (ATC, COVERT, SPT, LPT, EDD, WDD, WSPT and WPD). These generated competing heuristics were called ATC1, ATC2, ATC3, COV1, COV2, COV3, COV4, EDD1, EDD2, EDD3, WDD1, WDD2, WDD3, WSPT1, WSPT2, WSPT3, WPD1, WPD2, WPD3 and WPD4. The arrangements among the heuristics were made according to the double due date. The proposed NDR-D was applied to the generated heuristics and metaheuristics, simulated annealing and genetic algorithms, for a set of randomly generated problems. Problem sizes were chosen as 50, 70 and 100. In this study, 202,500 problems were randomly generated and used to demonstrate the performance of NDR-D. From the computational results, it can be clearly seen that the NDR-D dominates the generated heuristics and metaheuristics in all runs. Additionally, it is possible to see which heuristics are the best for the double due date single-machine TWT problems.