On the Calendar Planning Problem with Renewable Resource

摘要

We consider a strongly NP-hard calendar planning problem with constraints on resource consumption and job ordering. One characteristic feature of our problem setting is that resource consumption intensities by different jobs may change during their processing, and resource availability depends on time. To solve the problem, we construct an integer programming model and develop a dynamic programming algorithm. We distinguish a special case of the problem that can be solved in pseudopolynomial time. We show numerical experiments on randomly generated test examples.