The main contribution of this thesis is twofold. First, we propose a modeling approach that offers a generic framework to formulate various types of resource loading and RCCP problems as ILP models. Second, we propose various algorithms that can solve problems of reasonable size, i.e., typically encountered in practice, to optimality.
We position resource loading between strategical capacity planning (aggregate planning) and operational capacity planning (scheduling) as a tactical capacity planning problem. Resource loading has been rather underexposed both in the literature and in practice. As a tactical instrument it benefits the flexibility of the entire production system for various reasons. It serves as a tool in the customer order processing stage, which, in make-to-order manufacturing environments, is typically characterized by much uncertainty. On the demand side there is uncertainty as to what orders can eventually be acquired, while furthermore order characteristics are uncertain or at best partly known. On the supply side there is uncertainty in the availability of the resources. In these situations, a resource loading tool can be used to match production capacity and customer demand, while minimizing the cost of customer order tardiness and the use of nonregular capacity. Resource loading analyses can thus be used to accept/reject orders, or to quote reliable due dates. Resource loading can also serve as a tool to define realistic constraints for the underlying scheduling problem. The resource capacity levels and important milestones (such as release and due dates) are usually supposed to be fixed in scheduling. Resource loading can detect when and where difficulties will occur in scheduling at an early stage, and allocate orders or order parts more efficiently, and, if necessary, properly adjust resource capacity levels (by assigning nonregular capacity) and/or milestones.
In this thesis we propose a deterministic approach for modeling and solving resource loading problems. In order to smooth out the aforementioned uncertainty in resource loading problems we formulate resource loading at a higher level of aggregation than scheduling problems (i.e., the tactical level vs. the operational level). In resource loading problems we distinguish (customer) orders that consist of jobs. Jobs are in fact work packages at a higher level of aggregation. In the underlying shop floor scheduling problem, jobs may be further disaggregated into operations or tasks.
The difficulty of formulating the resource loading problem as an integer linear programming model is that modeling precedence relations is not straightforward, and the resulting formulations are often extremely hard to solve. We propose a modeling approach that offers a generic framework for modeling various resource loading problems. The proposed model can handle a large variety of practical aspects, such as generalized precedence constraints, various forms of capacity flexibility, due date driven resource loading, time driven resource loading, or a combination of these. In this modeling approach we make a distinction between order plans and order schedules. Order plans indicate in which periods a job of an order is allowed to be processed. Order schedules indicate which (part of the) jobs of the order are actually processed in each period. We propose a mixed-integer linear programming (MILP) model of the resource loading problem with an exponential number of integer variables. A relatively small and fixed part of these variables determine the required nonregular capacity usage per resource per period. The remaining variables are binary variables that correspond to selecting an order plan for an order. The order plans are thus columns of the coefficient matrix of the model, which are feasible with respect to precedence constraints and order release and due date constraints. The MILP model selects precisely one order plan per order, and determines order schedules that are consistent with these order plans. The model determines the nonregular capacity usage from the order schedules. The precedence relations and release and due date constraints thus do not have to be applied to the order schedules by the model, since they are embedded in the order plans. However, since there are exponentially many feasible order plans, an explicit model of a problem of regular size is impossible to formulate and solve. We therefore propose various exact and heuristic solution methods, which are all based on first solving the linear programming (LP) relaxation of this formulation by column generation. The pricing problem comprises the determination of feasible order plans with negative reduced costs. The idea of a column generation scheme is that only a small set of variables are required to determine the optimal solution of the LP. It starts from a restricted LP formulation (RLP), which has at least one order plan per order. After each RLP optimization, order plans with negative reduced costs are added to the RLP. The column generation scheme terminates when no order plans with negative reduced costs exist. The optimal solution of the LP is then found. Clearly, if the optimal solution of the linear programming relaxation happens to be integral, we have found an optimal solution for the resource loading problem. Otherwise, we apply a branch-and-price algorithm to determine an optimal solution. We propose various exact and heuristic branching strategies. Furthermore, we propose various approximation techniques that are based on the column generation approach, such as approximation algorithms that proceed by judiciously rounding the linear programming solution to obtain a feasible solution for the original problem.
Computational experiments with the resource loading methods show that large resource loading problems with a planning horizon of up to 15 weeks and 5 machine groups can usually be solved to optimality. For larger problems, the branch-and-bound methods usually have to be truncated. Various sensitivity analyses show that adding planning flexibility in some cases makes cases easier to solve, and in other cases makes it harder to prove optimality. The best resource loading method is a combination of two branching strategies. This (exact) method outperforms all approximation methods.
In resource loading problems we assume linear precedence relations. We also propose extensions of the algorithms that are able to deal with generalized precedence relations. This allows us to use the same model and solution methods to solve Multi-Project Rough-Cut Capacity Planning (RCCP) problems, for which some heuristics have already been proposed in the literature. The main algorithmic implication of the generalized precedence constraints is the generalization of the pricing algorithm. The pricing problem becomes much harder to solve, especially when the project size increases. We propose three different pricing algorithms, so that pricing problems of many sizes can be solved. We propose branch-and-bound algorithms that use one of these pricing algorithms to solve the linear program. We also propose approximation techniques, such as the rounding heuristics that we proposed for resource loading problems, and an improvement heuristic, which tries to improve an existing feasible solution.
Computational experiments with the branch-and-bound methods show that RCCP problems for projects of reasonable size can be solved to optimality. For larger problems, the branch-and-bound methods compete with the heuristics from the literature. For RCCP problems with very large projects solving the pricing problem often becomes too computational intensive. As a result, for large RCCP problems the branch-and-bound methods are outperformed by the heuristics from the literature. We note that, from a practical point of view, it is questionable whether it makes sense to solve such large problems to optimality, since information regarding resource availability and project characteristics are usually uncertain in the long term. Solving RCCP problems with a long planning horizon is thus more a mathematical challenge.