Abstract
We present a neuro-dominance rule for single machine total weighted tardiness problem with unequal release dates. To obtain the neuro-dominance rule (NDR), backpropagation artificial neural network (BPANN) has been trained using 10000 data and also tested using 10000 another data. The proposed neuro-dominance rule provides a sufficient condition for local optimality. It has been proved that if any sequence violates the neuro-dominance rule then violating jobs are switched according to the total weighted tardiness criterion. The proposed neuro-dominance rule is compared to a number of competing heuristics and meta heuristics for a set of randomly generated problems. Our computational results indicate that the neuro-dominance rule dominates the heuristics and meta heuristics in all runs. Therefore, the neuro-dominance rule can improve the upper and lower bounding schemes.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akturk, M.S., Ozdemir, D.: A new dominance rule to minimize total weighted tardiness with unequal release date. European Journal of Operational research 135, 394–412 (2001)
Chu, C., Portman, M.C.: Some new efficient methods to solve the n| 1 | r i | Σw i T i scheduling problem. European Journal of Operation Research 58, 404–413 (1992)
Rinnooy Kan, A.H.G.: Machine sceheduling problems: Classification complexity and omputations, Nijhoff, The Hague (1976)
Rachamadugu, R.M.V.: A note on weighted tardiness problem. Operations Research 23, 908–927 (1975)
Rinnooy Kan, A.H.G., Lageweg, B.J., Lenstra, J.K.: Minimizing total costs in one machine scheduling. Operations Research 23, 908–927 (1975)
Szwarc, W., Liu, J.J.: Weighted Tardines single machine scheduling with proportional weights. Management Science 39, 626–632 (1993)
Akturk, M.S., Yidirim, M.B.: A new lower bounding scheme for the total weighted tardiness problem. Computers and Operational Research 25(4), 265–278 (1998)
Cakar, T.: A New Neuro-dominance rule for single machine tardiness problem. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Laganá, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3483, pp. 1241–1250. Springer, Heidelberg (2005)
Chu, C.: A Branch-and-bound algorithm to minimize total tardiness with unequal release dates. Naval research logistics 39, 265–283 (1992)
Dessouky, M.I., Deogun, J.S.: Sequencing jobs with unequal ready times to inimize mean flow time. SIAM Journal of Computing 10, 192–202 (1981)
Bianco, L., Ricciardelli, S.: Sceheduling of a single machine to minimize total weighted completion time subject to release dates. Naval Research Logistics 29(1), 151–167 (1982)
Hariri, A.M.A., Potts, C.N.: An algorithm for single machine sequencing with release dates to minimize total weighted completion time. Discrete Applied Mathematics 5, 99–109 (1983)
Potts, C.N., Van Wassenhove, L.N.: A Branch and bound algorithm for total weighted tardiness problem. Operation Research 33, 363–377 (1985)
Vepsalainen, A.P.J., Morton, T.E.: Priority rules for job shops with weighted tardiness cost. Management Science 33, 1035–1047 (1987)
Potts, C.N., Van Wassenhove, L.N.: Dynamic programming and decomposition approaches for the single machine total tardiness problem. European Journal of Operation Research 32, 405–414 (1987)
Abdul-Razaq, T.S., Potts, C.N., Van Wassenhove, L.N.: A survey of algorithms for the single machine total weighted tardiness scheduling problem. Discrete Applied Mathematics 26, 235–253 (1990)
Sabuncuoglu, I., Gurgun, B.: A neural network model for scheduling problems. European Journal of Operational research 93(2), 288–299 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Çakar, T. (2006). A New Neuro-Dominance Rule for Single Machine Tardiness Problem with Unequal Release Dates. In: Kollias, S., Stafylopatis, A., Duch, W., Oja, E. (eds) Artificial Neural Networks – ICANN 2006. ICANN 2006. Lecture Notes in Computer Science, vol 4132. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11840930_100
Download citation
DOI: https://doi.org/10.1007/11840930_100
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38871-5
Online ISBN: 978-3-540-38873-9
eBook Packages: Computer ScienceComputer Science (R0)