In this paper we describe polynomial time algorithms for minimizing a separable convex function of the resource usage over time of a set of jobs with individual release dates and deadlines, and admitting a common processing time.

We consider single machine scheduling problems with additional non-renewable resource constraints. Examples for non-renewable resources include raw materials, energy, or money. Usually they have an initial stock and replenishments arrive over time at a-priori known time points and quantities. The jobs have some requirements from the resources and a job can only be started if the available quantity from each of the required resources exceeds the requirements of the job. Upon starting a job, it consumes its requirements which decreases the available quantities of the respective non-renewable resources. There is a broad background for this class of problems. Most of the literature concentrate on the makespan, and the maximum lateness objectives. This paper focuses on the total weighted completion time objective for which the list of the approximation algorithms is very short. We extend that list by considering new special cases and obtain new complexity results and approximation algorithms.

We study the resource loading problem, which arises in tactical capacity planning. In this problem, one has to plan the intensity of execution of a set of orders to minimize a cost function that penalizes the resource use above given capacity limits and the completion of the orders after their due dates. Our main contributions include a novel mixed-integer linear-programming (MIP)‐based formulation, the investigation of the polyhedra associated with the feasible intensity assignments of individual orders, and a comparison of our branch-and-cut algorithm based on the novel formulation and the related polyhedral results with other MIP formulations. The computational results demonstrate the superiority of our approach. In our formulation and in one of the proofs, we use fundamental results of Egon Balas on disjunctive programming.

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods.