Single machine scheduling problem with a common deadline and resource dependent release dates (Q1178528): Difference between revisions

We have \(n\) independent jobs which can be performed in a single machine so that each job runs in a non-interruptable time interval of length \(b_ i\), which is disjoint from the same interval of other jobs. Each job has a different availability time \(t_ i\) at the start. The jobs demand \(r_ i\) amounts of resource, and the \(i\)-th job must satisfy the following condition: \(t_ i=b_ i-a_ ir_ i\). The paper deals with the problem of minimizing the sum of used resources in a limited total schedule time. NP-completeness is proved in general, but approximate algorithms are given for some special cases. Some numerical examples were also tested.