Job-shop scheduling with resource-time models of operations (Q1820680)

A branch-and-bound algorithm is presented which solved the following version of the classical job-shop scheduling problem in which the processing times \(p_ j\) for the operations are replaced by functions of the form \(p_ j(u_ j)=b_ j-a_ ju_ j\) where \(b_ j\), \(a_ j>0\) are given. \(0\leq u_ j\leq \beta_ j\leq b_ j/a_ j\) is the amount of a continuously-divisible resource which can be allocated to operation \(0_ j\). How should a given amount U of the resource to be allocated to the operations such that an optimal job-shop schedule resulting from the allocation minimizes the total time of performing all operations? The algorithm is based on a disjunctive graph approach. Computational experience is reported.