Scheduling Jobs on Parallel Machines, each with a Unit-Capacity Buffer

Baas, S. M. and Kern, Walter and Nawijn, W. M. (1990) Scheduling Jobs on Parallel Machines, each with a Unit-Capacity Buffer.
Technical Report , 30 p.

Abstract

Given are a set of k parallel machines and a set of n jobs which arrive at fixed times. Each job has a fixed, but machine-dependend processing time and value. Each machine can process one job at a time. A job is processed either immediately after its time of arrival or after having spent some time in a buffer, or it is rejected. It is shown that under certain weak conditions the problem of finding a minimum weight schedule can be solved in polynomial time, but that it becomes NP-complete if such conditions do not hold.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr90-085
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 09 Jan 2012 11:48
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/85