NP-hardness of shop-scheduling problems with three jobs

0.00 Avg rating—0 Votes

Article ID:	iaor19971042
Country:	Netherlands
Volume:	59
Issue:	3
Start Page Number:	237
End Page Number:	266
Publication Date:	May 1995
Journal:	Discrete Applied Mathematics
Authors:	Shakhlevich N.V., Sotskov Yu. N.
Keywords:	computational analysis

Abstract:

This paper deals with the problem of scheduling n jobs on m machines in order to minimize the maximum completion time or mean flow time of jobs. The authors extend the results obtained by Sotskov on the complexity of shop-scheduling problems with n=3. The main result of this paper is an NP-hardness proof for scheduling 3 jobs on 3 machines, whether preemptions of operations are allowed or forbidden.

Reviews

Required fields are marked *. Your email address will not be published.