NEW HEURISTICS FOR MINIMISING TOTAL COMPLETION TIME AND THE NUMBER OF TARDY JOBS CRITERIA ON A SINGLE MACHINE WITH RELEASE TIME

E. O. Oyetunji, A. E. Oluleye

Abstract


ENGLISH ABSTRACT: This paper considers the bi-criteria scheduling problem of simultaneously minimising the total completion time and the number of tardy jobs with release dates on a single machine. Since the problem had been classified as NP-Hard, two heuristics (HR9 and HR10) were proposed for solving this problem. Performance evaluations of the proposed heuristics and selected solution methods (HR7 and BB) from the literature were carried out on 1,100 randomly generated problems ranging from 3 to 500 jobs. Experiment results show that HR7 outperformed HR10 when the number of jobs (n) is less than 30, while HR10 outperformed HR7 for n? 30.

AFRIKAANSE OPSOMMING: In hierdie artikel word die bi-kriteria-skeduleringsprobleem bestudeer waar die totale voltooiingstyd en die aantal take wat laat is op n enkele masjien geminimiseer moet word. Verskeie heuristieke word voorgestel en getoets om sodoende die beste benadering te identifiseer.


Keywords


NP-Hard; HR9 and HR10; HR7; posteriori approach;

Full Text:

PDF


DOI: https://doi.org/10.7166/21-2-53

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