HEURISTICS FOR MINIMIZING THE NUMBER OF TARDY JOBS ON A SINGLE MACHINE WITH RELEASE TIME

E. O. Oyetunji, A. E. Oluleye

Abstract


ENGLISH ABSTRACT: This paper considers the problem of minimizing the number of tardy jobs with release time on a single machine. Given that the problem has been classified as strongly NP-Hard, three heuristics (EOO, HR2, and HR3) are proposed for this problem. They are compared with a heuristic by Dauzere-Perez (selected from the literature). Randomly-generated problems ranging from 3 to 500 jobs are solved. Experimental results show that one of the proposed heuristics (EOO) outperforms other heuristics, both in terms of quality of solution (effectiveness) and speed of execution (efficiency).

AFRIKAANSE OPSOMMING: Die navorsing behandel die ministering van voltooiingstyd van die aantal draaltake by n enkele werktuig. As aanvaar word dat die problem geklassifiseer word as hoofsaaklike NP-hard, word voorgestel dat die vraagstuk bestudeer word deur gebruik te maak van drie heuristiese metodes (EOO, HR2, HR3). Die metodes word vergelyk ten opsigte van vertoning met die Dauzere-Perez-metode. Toevalsgegenereerde probleme wat strek vanaf 3 tot 500 draaltake word behandel. Die eksperimentele werk lewer bewys dat die EOO-metode ander metodes die loef afsteek ten opsigte van oplossingsgoedheid en snelheid.


Full Text:

PDF


DOI: https://doi.org/10.7166/19-2-100

Refbacks

  • There are currently no refbacks.




Copyright (c) 2015 The South African Journal of Industrial Engineering


ISSN 2224-7890 (on-line) ; ISSN 1012-277X (print)


Powered by OJS and hosted by Stellenbosch University Library and Information Service since 2011.


Disclaimer:

This journal is hosted by the SU LIS on request of the journal owner/editor. The SU LIS takes no responsibility for the content published within this journal, and disclaim all liability arising out of the use of or inability to use the information contained herein. We assume no responsibility, and shall not be liable for any breaches of agreement with other publishers/hosts.

SUNJournals Help