A branch and price solution approach for order acceptance and capacity planning in make-to-order operations

Make-to-order (MTO) operations have to effectively manage their capacity to make long-term sustainable profits. This objective can be met by selectively accepting available customer orders and simultaneously planning for capacity. We model a MTO operation of a job-shop with multiple resources having regular and non-regular capacity. The MTO firm has a set of customer orders at time zero with fixed due-dates. The process route, processing times, and sales price for each order are given. Since orders compete for limited resources, the firm can only accept some orders. In this paper a Mixed-Integer Linear Program (MILP) is proposed to aid an operational manager to decide which orders to accept and how to allocate resources such that the overall profit is maximized. A branch-and-price (B&P) algorithm is devised to solve the MILP effectively. The MILP is first decomposed into a master problem and several sub-problems using Dantzig-Wolfe decomposition. Each sub-problem is represented as a network flow problem and an exact procedure is proposed to solve the sub-problems efficiently. We also propose an approximate B&P scheme, Lagrangian bounds, and approximations to fathom nodes in the branch-and-bound tree. Computational analysis shows that the proposed B&P algorithm can solve large problem instances with relatively short time.     

Scheduling tests in automotive R&D projects

In automotive R&D projects a major part of development cost is caused by tests which utilize expensive experimental vehicles. In this paper, we introduce an approach for scheduling the individual tests such that the number of required experimental vehicles is minimized. The proposed approach is based on a new type of multi-mode resource-constrained project scheduling model with minimum and maximum time lags as well as renewable and cumulative resources. We propose a MILP formulation, which is solvable for small problem instances, as well as several variants of a priority-rule based method that serve to solve large problem instances. The developed solution methods are examined in a comprehensive computational study. For a real-world problem instance it is shown that the introduced approach may enhance the current methods applied in practice.     

A branch-and-price algorithm for a vehicle routing with demand allocation problem

We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.     

A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints

In this paper, we consider a two-machine flowshop scheduling problem in which the waiting time of each job between the two machines cannot be greater than a certain time period. For the problem with the objective of minimizing makespan, we identify several dominance properties of the problem and develop a branch-and-bound (B&B) algorithm using the dominance properties. Computational tests are performed on randomly generated test problems for evaluation of performance of the B&B algorithm, and results show that the algorithm can solve problems with up to 150 jobs in a reasonable amount of CPU time.     

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.     

Combining Metaheuristics and Exact Methods for Solving Exactly Multi-objective Problems on the Grid

This paper presents a parallel hybrid exact multi-objective approach which combines two metaheuristics – a genetic algorithm (GA) and a memetic algorithm (MA), with an exact method – a branch and bound (B&B) algorithm. Such approach profits from both the exploration power of the GA, the intensification capability of the MA and the ability of the B&B to provide optimal solutions with proof of optimality. To fully exploit the resources of a computational grid, the hybrid method is parallelized according to three well-known parallel models – the island model for the GA, the multi-start model for the MA and the parallel tree exploration model for the B&B. The obtained method has been experimented and validated on a bi-objective flow-shop scheduling problem. The approach allowed to solve exactly for the first time an instance of the problem – 50 jobs on 5 machines. More than 400 processors belonging to 4 different administrative domains have contributed to the resolution process during more than 6 days.      

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

Dismantling of nuclear power plants at optimal NPV

Today, worldwide far more than 100 nuclear power plants, which have been decommissioned in the recent years, are waiting for their complete dismantling. Since the dismantling of a single reactor causes costs of up to one billion Euros and lasts up to 15 years, the elaboration of a scheduling approach helping to optimize the net present value of a dismantling project seems to be worthwhile. In this paper we present a resource-constrained project scheduling approach optimizing the total discounted disbursements of dismantling a nuclear power plant. For the corresponding NP-hard optimization problem, we introduce an appropriate project scheduling model with minimum and maximum time lags, renewable and cumulative resources as well as multiple execution modes. To solve this model, we introduce a relaxation-based enumeration approach that delivers optimal solutions for problem instances containing up to 50 activities.     

Time slack-based techniques for robust project scheduling subject to resource uncertainty

The resource-constrained project scheduling problem (RCPSP) has been the subject of a great deal of research during the previous decades. This is not surprising given the high practical relevance of this scheduling problem. Nevertheless, extensions are needed to be able to cope with situations arising in practice such as multiple activity execution modes, activity duration changes and resource breakdowns. In this paper we analytically determine the impact of unexpected resource breakdowns on activity durations. Furthermore, using this information we develop an approach for inserting explicit idle time into the project schedule in order to protect it as well as possible from disruptions caused by resource unavailabilities. This strategy will be compared to a traditional simulation-based procedure and to a heuristic developed for the case of stochastic activity durations.     

Models and algorithms for three-stage two-dimensional bin packing

We consider the three-stage two-dimensional bin packing problem (2BP) which occurs in real-world applications such as glass, paper, or steel cutting. We present new integer linear programming formulations: models for a restricted version and the original version of the problem are developed. Both only involve polynomial numbers of variables and constraints and effectively avoid symmetries. Those models are solved using CPLEX. Furthermore, a branch-and-price (B&P) algorithm is presented for a set covering formulation of the unrestricted problem, which corresponds to a Dantzig-Wolfe decomposition of the polynomially-sized model. We consider column generation stabilization in the B&P algorithm using dual-optimal inequalities. Fast column generation is performed by applying a hierarchy of four methods: (a) a fast greedy heuristic, (b) an evolutionary algorithm, (c) solving a restricted form of the pricing problem using CPLEX, and finally (d) solving the complete pricing problem using CPLEX. Computational experiments on standard benchmark instances document the benefits of the new approaches: The restricted version of the integer linear programming model can be used to quickly obtain near-optimal solutions. The unrestricted version is computationally more expensive. Column generation provides a strong lower bound for 3-stage 2BP. The combination of all four pricing algorithms and column generation stabilization in the proposed B&P framework yields the best results in terms of the average objective value, the average run-time, and the number of instances solved to proven optimality.     

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.     

Scheduling in bicriteria single machine systems with past-sequence-dependent setup times and learning effects

Scheduling with setup times and learning plays a crucial role in today's manufacturing and service environments where scheduling decisions are made with respect to multiple performance criteria rather than a single criterion. In this paper, we address a bicriteria single machine scheduling problem with job-dependent past-sequence-dependent setup times and job-dependent position-based learning effects. The setup time and actual processing time of a job are respectively unique functions of the actual processing times of the already processed jobs and the position of the job in a schedule. The objective is to derive the schedule that minimizes a linear composite function of a pair of performance criteria consisting of the makespan, the total completion time, the total lateness, the total absolute differences in completion times, and the sum of earliness, tardiness, and common due date penalty. We show that the resulting problems cannot be solved in polynomial time; thus, branch-and-bound (B&B) methods are proposed to obtain the optimal schedules. Our computational results demonstrate that the B&B can solve instances of various size problems with attractive times.     

An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem

This paper investigates the construction of an automatic algorithm selection tool for the multi-mode resource-constrained project scheduling problem (MRCPSP). The research described relies on the notion of empirical hardness models. These models map problem instance features onto the performance of an algorithm. Using such models, the performance of a set of algorithms can be predicted. Based on these predictions, one can automatically select the algorithm that is expected to perform best given the available computing resources. The idea is to combine different algorithms in a super-algorithm that performs better than any of the components individually. We apply this strategy to the classic problem of project scheduling with multiple execution modes. We show that we can indeed significantly improve on the performance of state-of-the-art algorithms when evaluated on a set of unseen instances. This becomes important when lots of instances have to be solved consecutively. Many state-of-the-art algorithms perform very well on a majority of benchmark instances, while performing worse on a smaller set of instances. The performance of one algorithm can be very different on a set of instances while another algorithm sees no difference in performance at all. Knowing in advance, without using scarce computational resources, which algorithm to run on a certain problem instance, can significantly improve the total overall performance.     

Interactive analysis of multiple-criteria project scheduling problems

The paper considers an interactive search over a non-dominated solution space of a multiple-criteria project scheduling problem. The approach described handles quite a general class of non-preemptive project scheduling problems with renewable, non-renewable and doubly constrained resources, multiple performing modes of activities, precedence constraints in the form of an activity network and multiple project performance criteria of time and cost type. The approach consists of two stages. In the first stage, a large representative sample of approximately non-dominated schedules is generated by the Pareto Simulated Annealing (PSA) metaheuristic method. Then, in the second stage, an interactive search over the sample is organized by the `Light Beam Search' (LBS) procedure in its discrete version.     

A faster exact method for solving the robust multi-mode resource-constrained project scheduling problem

This paper presents a mixed-integer linear programming formulation for the multi-mode resource-constrained project scheduling problem with uncertain activity durations. We consider a two-stage robust optimisation approach and find solutions that minimise the worst-case project makespan, whilst assuming that activity durations lie in a budgeted uncertainty set. Computational experiments show that this easy-to-implement formulation is many times faster than the current state-of-the-art solution approach for this problem, whilst solving over 40% more instances to optimality over the same benchmarking set.     

Discrete and geometric Branch and Bound algorithms for?medical image registration

Aiming at the development of an exact solution method for registration problems, we present two different Branch & Bound algorithms for a mixed integer programming formulation of the problem. The first B&B algorithm branches on binary assignment variables and makes use of an optimality condition that is derived from a graph matching formulation. The second, geometric B&B algorithm applies a geometric branching strategy on continuous transformation variables. The two approaches are compared for synthetic test examples as well as for 2-dimensional medical data. The results show that medium sized problem instances can be solved to global optimality in a reasonable amount of time.     

Mixed-integer linear programming for resource leveling problems

We consider project scheduling problems subject to general temporal constraints, where the utilization of a set of renewable resources has to be smoothed over a prescribed planning horizon. In particular, we consider the classical resource leveling problem, where the variation in resource utilization during project execution is to be minimized, and the so-called “overload problem”, where costs are incurred if a given resource-utilization threshold is exceeded. For both problems, we present new mixed-integer linear model formulations and domain-reducing preprocessing techniques. In order to strengthen the models, lower and upper bounds for resource requirements at particular points in time, as well as effective cutting planes, are outlined. We use CPLEX 12.1 to solve medium-scale instances, as well as instances of the well-known test set devised by Kolisch et al. (1999). Instances with up to 50 activities and tight project deadlines are solved to optimality for the first time.