1997 | OriginalPaper | Chapter
Computational Complexity Analysis of Single Machine Scheduling Problems with Job Release Dates Dependent on Resources
Author : Adam Janiak
Published in: Operations Research Proceedings 1996
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Single machine scheduling problems with job release dates and technological precedence constraints among jobs are considered. It is assumed that job release dates depend on continuously-divisible resources such as: energy, fuel, catalyzer, row materials, financial outlay. The following optimization criteria are considered: makespan, total resource consumption and both simultaneously. Detailed computational complexity analysis of the considered problems and their special cases were conducted. It appears that some problems are NP-complete even for the some models of release dates for all jobs. Several special cases with polynomial time algorithms are found.