New computational results on the discrete time/cost trade-off problem in project networks

We describe a new exact procedure for the discrete time/cost trade-off problem in deterministic activity-on-the-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single resource (money) committed to it. The objective is to construct the complete and efficient time/cost profile over the set of feasible project durations. The procedure uses a horizon-varying approach based on the iterative optimal solution of the problem of minimising the sum of the resource use over all activities subject to the activity precedence constraints and a project deadline. This optimal solution is derived using a branch-and-bound procedure which computes lower bounds by making convex piecewise linear underestimations of the discrete time/cost trade-off curves of the activities to be used as input for an adapted version of the Fulkerson labelling algorithm for the linear time/cost trade-off problem. Branching involves the selection of an activity in order to partition its set of execution modes into two subsets which are used to derive improved convex piecewise linear underestimations. The procedure has been programmed in Visual C ++ under Windows NT and has been validated using a factorial experiment on a large set of randomly generated problem instances.     

Discrete time/cost trade-offs in project scheduling with time-switch constraints

The discrete time/cost trade-off problem assumes the duration of project activities to be discrete, non-increasing functions of the amount of a single non-renewable resource. The problem has been studied under three possible objectives. The so-called deadline problem involves the scheduling of project activities in order to minimize the total cost of the project while meeting a given deadline. The budget problem aims at minimizing the project duration without exceeding a given budget. A third objective involves the generation of the complete efficient time/cost profile over the set of feasible project durations. In this paper we describe a solution procedure for the deadline problem in which three special cases of time-switch constraints are involved. These constraints impose a specified starting time on the project activities and force them to be inactive during specified time periods. We propose a branch-and-bound algorithm and a heuristic procedure which both make use of a lower bound calculation for the discrete time/cost trade-off problem (without time-switch constraints). The procedures have been coded in Visual C++, version 6.0 under Windows 2000 and have been validated on a randomly generated problem set. We also discuss an illustrative example based on a real-life situation.     

Selection of Capacity Expansion Projects

The problem of determining a project selection schedule and a production-distribution-inventory schedule for each of a number of plants so as to meet the demands of multiregional markets at minimum discounted total cost during a discrete finite planning horizon is considered. We include the possibility of using inventory and/or imports to delay the expansion decision at each producing region in a transportation network. Through a problem reduction algorithm, the Lagrangean relaxation problem strengthened by the addition of a surrogate constraint becomes a 0–1 mixed integer knapsack problem. Its optimal solution, given a set of Lagrangean multipliers, can be obtained by solving at most two generally smaller 0–1 pure integer knapsack problems. The bound is usually very tight. At each iteration of the subgradient method, we generate a primal feasible solution from the Lagrangean solution. The computational results indicate that the procedure is effective in solving large problems to within acceptable error tolerances.     

Pareto ant colony optimization with ILP preprocessing in multiobjective project portfolio selection

One of the most important, common and critical management issues lies in determining the “best” project portfolio out of a given set of investment proposals. As this decision process usually involves the pursuit of multiple objectives amid a lack of a priori preference information, its quality can be improved by implementing a two-phase procedure that first identifies the solution space of all efficient (i.e., Pareto-optimal) portfolios and then allows an interactive exploration of that space. However, determining the solution space is not trivial because brute-force complete enumeration only solves small instances and the underlying NP-hard problem becomes increasingly demanding as the number of projects grows. While meta-heuristics in general provide an attractive compromise between the computational effort necessary and the quality of an approximated solution space, Pareto ant colony optimization (P-ACO) has been shown to perform particularly well for this class of problems. In this paper, the beneficial effect of P-ACO’s core function (i.e., the learning feature) is substantiated by means of a numerical example based on real world data. Furthermore, the original P-ACO approach is supplemented by an integer linear programming (ILP) preprocessing procedure that identifies several efficient portfolio solutions within a few seconds and correspondingly initializes the pheromone trails before running P-ACO. This extension favors a larger exploration of the search space at the beginning of the search and does so at a low cost.     

A biased random-key genetic algorithm for the project scheduling problem with flexible resources

In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an \(\mathcal {NP}\)-hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions.     

Exploiting process plan flexibility in production scheduling: A multi-objective approach

When solving a product/process design problem, we must exploit the available degrees of freedom to cope with a variety of issues. Alternative process plans can be generated for a given product, and choosing one of them has implications on manufacturing functions downstream, including planning/scheduling. Flexible process plans can be exploited in real time to react to machine failures, but they are also relevant for off-line scheduling. On the one hand, we should select a process plan in order to avoid creating bottleneck machines, which would deteriorate the schedule quality; on the other one we should aim at minimizing costs. Assessing the tradeoff between these possibly conflicting objectives is difficult; actually, it is a multi-objective problem, for which available scheduling packages offer little support. Since coping with a multi-objective scheduling problem with flexible process plans by an exact optimization algorithm is out of the question, we propose a hierarchical approach, based on a decomposition into a machine loading and a scheduling sub-problem. The aim of machine loading is to generate a set of efficient (non-dominated) solutions with respect to the load balancing and cost objectives, leaving to the user the task of selecting a compromise solution. Solving the machine loading sub-problem essentially amounts to selecting a process plan for each job and to routing jobs to the machines; then a schedule must be determined. In this paper we deal only with the machine loading sub-problem, as many scheduling methods are already available for the problem with fixed process plans. The machine loading problem is formulated as a bicriterion integer programming model, and two different heuristics are proposed, one based on surrogate duality theory and one based on a genetic descent algorithm. The heuristics are tested on a set of benchmark problems.     

A new path-based cutting plane approach for the discrete time-cost tradeoff problem

Determining discrete time-cost tradeoffs in project networks allows for the control of the processing time of an activity via the amount of non-renewable resources allocated to it. Larger resource allocations with associated higher costs reduce activities’ durations. Given a set of execution modes (time-cost pairs) for each activity, the discrete time-cost tradeoff problem (DTCTP) involves selecting a mode for each activity so that either: (i) the project completion time is minimized, given a budget, or (ii) the total project cost is minimized, given a deadline, or (iii) the complete and efficient project cost curve is constructed over all feasible project durations. The DTCTP is a problem with great applicability prospects but at the same time a strongly N P{\mathcal N}\,P-hard optimization problem; solving it exactly has been a real challenge. Known optimal solution methodologies are limited to networks with no more than 50 activities and only lower bounds can be computed for larger, realistically sized, project instances. In this paper, we study a path-based approach to the DTCTP, in which a new path-based formulation in activity-on-node project networks is presented. This formulation is subsequently solved using an exact cutting plane algorithm enhanced with speed-up techniques. Extensive computational results reported for almost 5,000 benchmark test problems demonstrate the effectiveness of the proposed algorithm in solving to optimality for the first time some of the hardest and largest instances in the literature. The promising results suggest that the algorithms may be embedded into project management software and, hence, become a useful tool for practitioners in the future.     

Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem

The time/cost trade-off models in project management aim to reduce the project completion time by putting extra resources on activity durations. The budget problem in discrete time/cost trade-off scheduling selects a time/cost mode for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally and each solution may have a different total cost value. In this study we consider the budget problem and aim to find the minimum cost solution among the minimum project completion time solutions. We analyse the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by branch and bound based optimization and heuristic algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the heuristic algorithms produce high quality solutions very quickly.     

Successive search methods for solving a canonical DC programming problem

In this article, we propose two successive search methods for solving a canonical DC programming problem constrained by the difference set between two compact convex sets in the case where the dimension number is greater than or equal to three. In order to find feasible solutions, the algorithms generate the directions based on a branch and bound procedure, successively. By exploring the provisional solutions throughout the intersection of the boundaries of two compact convex sets, both algorithms calculate an approximate solution.     

RAMP for the capacitated minimum spanning tree problem

This paper introduces dual and primal-dual RAMP algorithms for the solution of the capacitated minimum spanning tree problem (CMST). A surrogate constraint relaxation incorporating cutting planes is proposed to explore the dual solution space. In the dual RAMP approach, primal-feasible solutions are obtained by simple tabu searches that project dual solutions onto primal feasible space. A primal-dual approach is achieved by including a scatter search procedure that further exploits the adaptive memory framework. Computational results from applying the methods to a standard set of benchmark problems disclose that the dual RAMP algorithm finds high quality solutions very efficiently and that its primal-dual enhancement is still more effective.     

A Constraint-Based Method for Project Scheduling with Time Windows

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.     

The maximum return-on-investment plant location problem

The standard plant location problem determines which plants to open from a set of potential sites in order to satisfy the demands at a set of customer vertices at a minimum total cost. However, the optimal solution may exceed a limit on investment costs imposed on the enterprise in a practical setting. This paper examines the plant location problem in an environment in which the investment in plant and equipment is also an objective to be minimised. The problem is posed as a bicriterion model which examines the tradeoff between the sum of operational and investment costs and investment cost (or total cost vs sunk cost). A weighting method is used to generate efficient solutions, one of which is shown to maximise the return on investment. The integer-friendliness of the LP relaxation is investigated.     

A prototype column generation strategy for the multiple container loading problem

The multiple container loading cost minimization problem (MCLCMP) is a practical and useful problem in the transportation industry, where products of various dimensions are to be loaded into containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally formulated as a set cover problem and solved using column generation techniques, which is a popular method for handling huge numbers of variables. However, the direct application of column generation is not effective because feasible solutions to the pricing subproblem is required, which for the MCLCMP is NP-hard. We show that efficiency can be greatly improved by generating prototypes that approximate feasible solutions to the pricing problem rather than actual columns. For many hard combinatorial problems, the subproblem in column generation based algorithms is NP-hard; if suitable prototypes can be quickly generated that approximate feasible solutions, then our strategy can also be applied to speed up these algorithms.     

Searching optimal resequencing and feature assignment on an automated assembly line

The resequencing and feature assignment problem (RFAP) appears among jobs in the assembly line, especially in the automotive industry. Each job in the assembly line must be assigned a feature from its feasible feature set. However, a changeover cost is incurred between two consecutive jobs with different features. To minimize the total changeover cost, the job sequence needs to be rearranged, but the rearrangement is restricted to the number of offline buffers. The RFAP turns out to be ????-hard in the strong sense. Based on a beam search heuristic to generate upper bounds of optimum solutions, we have proposed an iterative search scheme which can achieve optimum solutions in a reasonably short time, for cases sized as large as that in reality. Extensive experiments have shown very favourable results for our methods in terms of both the solution quality and the time efficiency.     

Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers

This paper reports on a new solution approach for the well-known multi-mode resource-constrained project scheduling problem (MRCPSP). This problem type aims at the selection of a single activity mode from a set of available modes in order to construct a precedence and a (renewable and non-renewable) resource feasible project schedule with a minimal makespan. The problem type is known to be NP-hard and has been solved using various exact as well as (meta-)heuristic procedures.The new algorithm splits the problem type into a mode assignment and a single mode project scheduling step. The mode assignment step is solved by a satisfiability (SAT) problem solver and returns a feasible mode selection to the project scheduling step. The project scheduling step is solved using an efficient meta-heuristic procedure from literature to solve the resource-constrained project scheduling problem (RCPSP). However, unlike many traditional meta-heuristic methods in literature to solve the MRCPSP, the new approach executes these two steps in one run, relying on a single priority list. Straightforward adaptations to the pure SAT solver by using pseudo boolean non-renewable resource constraints has led to a high quality solution approach in a reasonable computational time. Computational results show that the procedure can report similar or sometimes even better solutions than found by other procedures in literature, although it often requires a higher CPU time.     

An algorithm for solving the multi-period online fulfillment assignment problem

This paper develops an optimal solution procedure for the multi-period online fulfillment assignment problem to determine how many and which of a retailer/e-tailer’s capacitated regional warehouse locations should be set up to handle online sales over a finite planning horizon. To reduce the number of candidate solutions in each period, dominance rules from the facility location literature are extended to handle the nonlinear holding and backorder cost implications of our problem. Computational results indicate that multi-period considerations can play a major role in determining the optimal set of online fulfillment locations. In 92% of our test problems, the multi-period solution incorporated fewer openings and closings than myopic single period solutions. To illustrate the use of the model under changing demands, the multi-period solution yielded different supply chain configurations than the myopic single period solution in over 37% of the periods.     

Constructing Good Solutions for the Spanish School Timetabling Problem

In the school timetabling problem a set of lessons (combinations of classes, teachers, subjects and rooms) has to be scheduled within the school week. Considering classes, teachers and rooms as resources for the lessons, the problem may be viewed as the scheduling of a project subject to resource constraints. We have developed an algorithm with three phases. In Phase I an initial solution is built by using the scheme of parallel heuristic algorithm with priority rules, but imbedding at each period the construction of a maximum cardinality independent set on a resource graph. In Phase II a tabu search procedure starts from the solution of Phase I and obtains a feasible solution to the problem. The solution obtained is improved in Phase III. Several procedures based on the calculation of negative cost cycles and shortest paths in a solution graph are used to get more compact timetables.The algorithms have been imbedded in a package designed to solve the problem for Spanish secondary schools. The computational results show its performance on a set of real problems. Nevertheless, it can be applied to more general problems and results on a set of large random problems are also provided.     

Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design

In this paper, we propose a path relinking procedure for the fixed-charge capacitated multicommodity network design problem. Cycle-based neighbourhoods are used both to move along paths between elite solutions and to generate the elite candidate set by a tabu-like local search procedure. Several variants of the method are implemented and compared. Extensive computational experiments indicate that the path relinking procedure offers excellent results. It systematically outperforms the cycle-based tabu search method in both solution quality and computational effort and offers the best current meta-heuristic for this difficult class of problems.     

On Resource Allocation Problems with Interval-Scale Coefficients

In this paper we discuss the classical problem of the allocation of a single finite resource among many competing activities for the specific case where the coefficients of the objective function form an interval scale. In this case there is no longer a single optimal solution, but rather a set of efficient solutions. We recommend a technique equivalent to parametric objective function analysis to generate the set of efficient solutions to the problem.     

Using Efficient Anchoring Points for Generating Search Directions in Interior Multiobjective Linear Programming

This paper modifies the affine-scaling primal algorithm to multiobjective linear programming (MOLP) problems. The modification is based on generating search directions in the form of projected gradients augmented by search directions pointing toward what we refer to as anchoring points. These anchoring points are located on the boundary of the feasible region and, together with the current, interior, iterate, define a cone in which we make the next step towards a solution of the MOLP problem. These anchoring points can be generated in more than one way. In this paper we present an approach that generates efficient anchoring points where the choice of termination solution available to the decision maker at each iteration consists of a set of efficient solutions. This set of efficient solutions is being updated during the iterative process so that only the most preferred solutions are retained for future considerations. Current MOLP algorithms are simplex-based and make their progress toward the optimal solution by following an exterior trajectory along the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an acceptable solution may prove less sensitive to problem size. We refer to the resulting class of MOLP algorithms that are based on the affine-scaling primal algorithm as affine-scaling interior multiobjective linear programming (ASIMOLP) algorithms.