{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T12:05:55Z","timestamp":1778587555610,"version":"3.51.4"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03n04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1994,12]]},"abstract":"<jats:p> The problem of nonpreemptively scheduling a set of n independent jobs with identical release times so as to minimize the number of late jobs is considered. It is known that the problem can be solved in O(n log n) time, by an algorithm due to Moore, for a single processor, and that it becomes NP-hard for two or more identical processors, even if all jobs have identical due dates. In this paper we give a fast heuristic, based on Moore\u2019s algorithm, for the multiprocessor case. Like Moore\u2019s algorithm, our heuristic also admits an O(n log n) implementation. It is shown that the performance ratio of the heuristic is 4\/3 for two identical processors, where the performance ratio is defined to be the least upper bound of the ratio of the number of on-time jobs in an optimal schedule versus that in the schedule generated by the heuristic. <\/jats:p>","DOI":"10.1142\/s0129054194000141","type":"journal-article","created":{"date-parts":[[2004,11,19]],"date-time":"2004-11-19T02:21:13Z","timestamp":1100830873000},"page":"261-279","source":"Crossref","is-referenced-by-count":7,"title":["HEURISTIC FOR MINIMIZING THE NUMBER OF LATE JOBS ON TWO PROCESSORS"],"prefix":"10.1142","volume":"05","author":[{"given":"JOSEPH Y-T.","family":"LEUNG","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering,  University of Nebraska-Lincoln, Lincoln, NE 68588\u20130115, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VINCENT K.M.","family":"YU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering,  University of Nebraska-Lincoln, Lincoln, NE 68588\u20130115, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054194000141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:44:08Z","timestamp":1565138648000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054194000141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":0,"journal-issue":{"issue":"03n04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1994,12]]}},"alternative-id":["10.1142\/S0129054194000141"],"URL":"https:\/\/doi.org\/10.1142\/s0129054194000141","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}