Resource constrained chain scheduling of uet jobs on two machines

W. Kubiak, J. BŁazewicz, M. Dror, N. Katoh, H. Rock

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


A well-known technique for solving scheduling problems with two identical parallel processors and unit execution time jobs under a makespan minimization criteria involves finding maximum cardinality matchings in the graph associated with the problem, and then using these matchings to create optimal schedules. For some problem instances, however, this method will not work, since the problems are NP-hard. In this note, a previously open problem involving additional resource constraints is shown to have a polynomial algorithm using cardinality matching method.

Original languageEnglish (US)
Pages (from-to)742-746
Number of pages5
JournalOperations Research
Issue number5
StatePublished - 1998
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Resource constrained chain scheduling of uet jobs on two machines'. Together they form a unique fingerprint.

Cite this