ON SCHEDULING INDEPENDENT TASKS WITH RESTRICTED EXECUTION TIMES.

Joseph Y.T. Leung

Research output: Contribution to conferencePaperpeer-review

Abstract

The problem of nonpreemptively scheduling n independent tasks on m identical and parallel machines with the objective of minimizing the overall finishing time is considered. The problem has been shown to be NP-complete in the strong sense and hence there probably will not be any pseudo-polynomial time algorithm for solving this problem. It is shown that if the execution times are restricted to a fixed number, say k, of different values, then it can be solved in polynomial time.

Original languageEnglish (US)
Pages471-479
Number of pages9
StatePublished - 1981
EventProc Annu Allerton Conf Commun Control Comput 18th - Monticello, IL, USA
Duration: Oct 8 1980Oct 11 1980

Conference

ConferenceProc Annu Allerton Conf Commun Control Comput 18th
CityMonticello, IL, USA
Period10/8/8010/11/80

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'ON SCHEDULING INDEPENDENT TASKS WITH RESTRICTED EXECUTION TIMES.'. Together they form a unique fingerprint.

Cite this