Computational Complexity Analysis of Single Machine Scheduling Problems with Job Release Dates Dependent on Resources

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.