A cutting plane approach for integrated planning and scheduling

In this paper we propose a branch-and-cut algorithm for solving an integrated production planning and scheduling problem in a parallel machine environment. The planning problem consists of assigning each job to a week over the planning horizon, whereas in the scheduling problem those jobs assigned to a given week have to be scheduled in a parallel machine environment such that all jobs are finished within the week. We solve this problem in two ways: (1) as a monolithic mathematical program and (2) using a hierarchical decomposition approach in which only the planning decisions are modeled explicitly, and the existence of a feasible schedule for each week is verified by using cutting planes. The two approaches are compared with extensive computational testing.     

Exact methods for the resource levelling problem

We present a project scheduling problem subject to general temporal constraints where the utilization of a set of renewable resources has to be smoothed over time. For solving the NP-hard optimization problem, we point out some important structural properties and introduce a new enumeration scheme. Combining this enumeration scheme with some branch-and-bound techniques, we propose an appropriate solution procedure for the project scheduling problem at hand. To outline the practical importance of resource levelling, we sketch exemplary the optimization of mid-term planning schedules with regard to the resource requirements of IT projects. Finally, we present results from a comprehensive computational study on problem instances of the well-known rlp_j10 and rlp_j20 test sets devised by Kolisch et al. (Benchmark Instances for Project Scheduling Problems, Kluwer, Boston, 1999).     

Heuristic solutions to the long-term unit commitment problem with cogeneration plants

We consider a long-term version of the unit commitment problem that spans over one year divided into hourly time intervals. It includes constraints on electricity and heating production as well as on biomass consumption. The problem is of interest for scenario analysis in long-term strategic planning. We model the problem as a large mixed integer programming problem. Two solutions to this problem are of interest but computationally intractable: the optimal solution and the solution derived by market simulation. To achieve good and fast approximations to these two solutions, we design heuristic algorithms, including mixed integer programming heuristics, construction heuristics and local search procedures. Two setups are the best: a relax and fix mixed integer programming approach with an objective function reformulation and a combination of a dispatching heuristic with stochastic local search. The work is developed in the context of the Danish electricity market and the computational analysis is carried out on real-life data.     

The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

We consider the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup costs and non-zero setup times, with the additional feature that setups may be carried over from one period to the next, and that setups are preserved over idle periods. We provide an exact formulation of this problem as a mixed-integer program.It is well known that the CLSP is NP-hard. Therefore, we have also developed a heuristic for solving large problem instances. This is coupled with a procedure for obtaining a lower bound on the optimal solution. We carry out a computational study to test the accuracy of several different lower bounding linear relaxations and the approximate solution obtained by the heuristic. In our study, the average deviation of the heuristic solution from the corresponding exact solution depends on the size of the problem and ranges from 10 to 16%. The heuristic is more effective when there are many more products than there are planning periods. This is a desirable property from a practical viewpoint since most firms are likely to implement such a procedure on a rolling horizon basis, solving the problem repeatedly for a few periods at a time.     

Precedence-constrained path planning of messenger UAV for air-ground coordination

This paper addresses an unmanned aerial vehicle (UAV) path planning problem for a team of cooperating heterogeneous vehicles composed of one UAV and multiple unmanned ground vehicles (UGVs). The UGVs are used as mobile actuators and scattered in a large area. To achieve multi-UGV communication and collaboration, the UAV serves as a messenger to fly over all task points to collect the task information and then flies all UGVs to transmit the information about tasks and UGVs. The path planning of messenger UAV is formulated as a precedence-constrained dynamic Dubins traveling salesman problem with neighborhood (PDDTSPN). The goal of this problem is to find the shortest route enabling the UAV to fly over all task points and deliver information to all requested UGVs. When solving this path planning problem, a decoupling strategy is proposed to sequentially and rapidly determine the access sequence in which the UAV visits task points and UGVs as well as the access location of UAV in the communication neighborhood of each task point and each UGV. The effectiveness of the proposed approach is corroborated through computational experiments on randomly generated instances. The computational results on both small and large instances demonstrate that the proposed approach can generate high-quality solutions in a reasonable time as compared with two other heuristic algorithms.     

Computational enhancements to fluence map optimization for total marrow irradiation using IMRT

The fluence map optimization (FMO) problem is a core problem in intensity modulated radiation therapy (IMRT) treatment planning. Although it has been studied extensively for site-specific treatment planning, few studies have examined efficient computational methods for solving it for intensity modulated total marrow irradiation (IM-TMI) planning; few studies have also looked at exploiting prior beamlet information to solve the FMO problem in a beam orientation optimization context. In this study, we consider different types of line search strategies and different types of warm-start techniques to improve the speed with which the FMO problem for IM-TMI is solved and the quality of the end solution. We also consider a parallelism-enhanced algorithm to solve the FMO problem for IM-TMI treatment planning with a large number of beams (36 equispaced beams at each of 11 isocenters, for a total of 396 beams). We show that the backtracking line search strategy with step reduction exhibits the best performance and that using either of the two types of warm-start techniques which we consider leads to significant improvements in both solution time and quality. We also provide results for the aforementioned 396-beam plan and show that 30-beam solutions obtained using beam orientation optimization attain a comparable level of quality as this larger solution.     

Methods based on discrete optimization for finding road network rehabilitation strategies

We study a dynamic optimization problem arising in the (long-term) planning of road rehabilitation activities. In this area one seeks a pavement resurfacing plan for a road network under budget constraints. Our main approach is to model this as an integer programming problem with underlying dynamic programming structure. We investigate properties of this model and propose a solution method based on Lagrangian relaxation where one gets subproblems that are shortest path problems. Some computational experiences based on realistic data are reported.     

Coverage of a Planar Point Set With Multiple Robots Subject to Geometric Constraints

This paper focuses on the assignment of N discrete points among K geometrically constrained robots and determination of the order in which the points should be processed by the robots. This path planning problem is directly motivated by an industrial laser drilling system with two robots that are constrained to translate along a common line while satisfying collision avoidance constraints. The points lie on a planar base plate that translates normal to the axis of motion of the robots. The geometric constraints on the motions of the robots lead to constraints on points that can be processed simultaneously.We use a two step approach to solve the path planning problem: (1) Splitting Problem: Assign the points to the K robots, subject to geometric constraints, to maximize parallel processing of the points. (2) Ordering Problem: Find an order of processing the split points by formulating and solving a multidimensional Traveling Salesman Problem (TSP) in the if-tuple space with an appropriately defined metric to minimize the total travel cost. For K = 2, we solve the splitting problem optimally in O(N³) time by converting it to a maximum cardinality matching problem. Since this is too slow for large datasets, we also provide a greedy O(N log N) algorithm. We provide computational results showing that the greedy algorithm solution is very close to the optimal solution for large datasets. For the ordering problem we present local search based heuristics to improve the multidimensional TSP tour. We give computational results for the ordering problem and for the overall performance gain obtained (over a single robot system) by using our algorithm. Finally, we extend our approach to a K-robot system and give computational results for K = 4.     

Parallel processing applied to the planning of hydrothermal systems

The objective of the long-term operating planning problem is to determine the optimum strategy for the generation of electricity, aiming toward the minimization of total operating cost over the planning period. In a competitive electricity market, with the participation of a significant number of hydroplants, such as in Brazil, precision modelling for operating planning is required so that a better use of hydraulic resources can be obtained. We present a long-term operating planning model based on an individual power plant representation. In order to support the high computational burden, a suitable parallel processing algorithm is proposed.     

Dynamic teams of robots as ad hoc distributed computers: reducing the complexity of multi-robot motion planning via subspace selection

We solve the multi-robot path planning problem using three complimentary techniques: (1) robots that must coordinate to avoid collisions form temporary dynamic teams. (2) Robots in each dynamic team become a distributed computer by pooling their computational resources over ad hoc wireless Ethernet. (3) The computational complexity of each team’s problem is reduced by carefully constraining the environmental subspace in which the problem is considered. An important contribution of this work is a method for quickly choosing the subspace, used for (3), to which each team’s problem is constrained. The heuristic is based on a tile-like pebble motion game, and returns true only if a subset of the environment will permit a solution to be found (otherwise it returns false). We perform experiments with teams of four and six CU Prairiedog robots (built on the iRobot Create platform) deployed in a large residence hall, as well as ten robots in random simulated environments.     

An exact approach to the problem of extracting an embedded network matrix

We study the problem of detecting a maximum embedded network submatrix in a {−1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0–1 integer linear programming formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an optimal solution to the problem. Some computational experiments are carried out over a set of instances available in the literature as well as over a set of random instances.     

New heuristics for planning operating rooms

We tackle the operating room planning problem of the Plastic Surgery and Major Burns Specialty of the University Hospital “Virgen del Rocio” in Seville (Spain). The decision problem is to assign an intervention date and an operating room to a set of surgeries on the waiting list, minimizing access time for patients with diverse clinical priority values. This problem has been previously addressed in the literature considering different objective functions. The clinical priority depends on the surgery priority and the number of days spent on the waiting list. We propose a set of 83 heuristics (81 constructive heuristics, a composite heuristic, and a meta-heuristic) based on a new solution encoding, and we compare these methods against existing heuristics from the literature for solving operating room planning problems. The heuristics are adapted to the problem under consideration (i.e. considering all constraints and the new objective function), being re-implemented using the information provided by the authors. In total, after a calibration procedure, we compare 17 heuristics. The computational experiments show that our proposed meta-heuristic is the best for the problem under consideration. Finally, the proposed heuristics are tested using data from the Plastic Surgery and Major Burns Specialty. The results show significant improvements on several key performance indicators (number of scheduled surgeries, quality of surgical plan, resources utilization, etc.) when comparing with the actual results obtained by the specialty in the current practice. The aforementioned hospital is currently implementing the heuristic methods.     

Robust capacitated facility location model for acquisitions under uncertainty

We study a new robust formulation for strategic location and capacity planning considering potential company acquisitions under uncertainty. Long-term logistics network planning is among the most difficult decisions for supply-chain managers. While costs, demands, etc. may be known or estimated well for the short-term, their future development is uncertain and difficult to predict.A new model formulation for the robust capacitated facility location problem is presented to cope with uncertainty in planning. Minimizing the expectation of the relative regrets across scenarios over multiple periods is the objective. It is achieved by dynamically assigning multi-level production allocations, locations and capacity adjustments for uncertain parameter development over time. Considering acquisitions for profit maximization and its supply-chain impact is new as well as the simultaneous decision of capacity adjustment and facility location over time. The solution of the novel robust formulation provides a single setup where good results can be achieved for any realized scenario. Hence, the solution may not be optimal for one particular scenario but may be good, i.e. the highest expected profit to gain, for any highly probable future realization. We show that robust mixed-integer linear programming model achieves superior results to the deterministic configurations in exhaustive computational tests. This dynamic robust formulation allows the supply-chain to favorably adapt to acquisitions and uncertain developments of revenue, demand and costs and hence reduces the potential negative impacts of uncertainty on supply-chain operations.     

Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms

The problem of integrating task assignment and planning paths for a group of cooperating uninhabited aerial vehicles, servicing multiple targets, is addressed. In the problem of interest the uninhabited aerial vehicles need to perform multiple consecutive tasks cooperatively on each ground target. A Dubins car model is used for motion planning, taking into account each vehicle's specific constraint of minimum turn radius. By using a finite set to define the visitation angle of a vehicle over a target we pose the integrated problem of task assignment and path optimization in the form of a graph. This new approach results in suboptimal trajectory assignments. Refining the visitation angle discretization allows for an improved solution. Due to the computational complexity of the resulting combinatorial optimization problem, we propose genetic algorithms for the stochastic search of the space of solutions. We distinguish between two cases of vehicle group composition: homogeneous, where all vehicles are identical; and heterogeneous, where the vehicles may have different operational capabilities and kinematic constraints. The performance of the genetic algorithms is demonstrated through sample runs and a Monte Carlo simulation study. Results show that the algorithms quickly provide good feasible solutions, and find the optimal solution for small sized problems.     

Optimized planning of frequency hopping in cellular networks

We consider a generalization of the classical frequency assignment problem. The generalization arises when frequency hopping is used in a cellular network. The planning problem concerns assigning lists of frequencies to blocks of transceivers, such that the total interference is minimized. This problem is considerably more difficult than the classical frequency assignment problem, because of the large number of possible frequency lists. We provide the technical background that motivates our study, and present a mathematical model which includes the classical frequency assignment problem as a special case. We describe a simulated annealing algorithm. The algorithm explores the solution space by solving an integer program in each iteration. We report computational results for real-life and synthesized networks.     

Exploring the Difficulties African-American Middle School Girls Face Enacting Computational Algorithmic Thinking over three Years while Designing Games for Social Change

Computational algorithmic thinking (CAT) is the ability to design, implement, and assess the implementation of algorithms to solve a range of problems. It involves identifying and understanding a problem, articulating an algorithm or set of algorithms in the form of a solution to the problem, implementing that solution in such a way that the solution solves the problem, and evaluating the solution based on some set of criteria. CAT is an important scaffolded on-ramp as students develop more advanced computational thinking capabilities and apply computational thinking to solve problems that are more constrained and require greater expertise. Supporting Computational Algorithmic Thinking (SCAT) is both a longitudinal between-subjects research project and a free enrichment program supporting and guiding African-American middle school girls over three years as they iteratively design a set of complex games for social change. This article explores Scholars’ reflections about the difficulties they faced while using CAT capabilities as they engaged in collaborative game design for social change over those three years. We particularly focus on how these difficulties changed over the course of three years as well as new difficulties that emerged from year to year as Scholars become more expert game designers and computational algorithmic thinkers.     

Movement Planning in the Presence of Flows

This paper investigates the problem of time-optimum movement planning in two and three dimensions for a point robot which has bounded control velocity through a set of n polygonal regions of given translational flow velocities. This intriguing geometric problem has immediate applications to macro-scale motion planning for ships, submarines, and airplanes in the presence of significant flows of water or air. Also, it is a central motion planning problem for many of the meso-scale and micro-scale robots that have been constructed recently, that have environments with significant flows that affect their movement. In spite of these applications, there is very little literature on this problem, and prior work provided neither an upper bound on its computational complexity nor even a decision algorithm. It can easily be seen that an optimum path for the 2D version of this problem can consist of at least an exponential number of distinct segments through flow regions. We provide the first known computational complexity hardness result for the 3D version of this problem; we show the problem is PSPACE hard. We give the first known decision algorithm for the 2D flow path problem, but this decision algorithm has very high computational complexity. We also give the first known efficient approximation algorithms with bounded error.     

Heuristics for capacity planning problems with congestion

Motivated by a problem in the semiconductor industry, we develop improved formulations for the problem of planning capacity acquisition and deletion over time when resources are subject to congestion, motivated by a problem in the semiconductor industry. We use nonlinear clearing functions to relate the expected output of a production resource in a planning period to the expected work in process (WIP) inventory level. Exploiting the properties of the clearing function allows us to formulate the single workcenter problem as a shortest path problem. This forms the basis for two greedy constructive heuristics and a Lagrangian heuristic for the multistage problem. The latter procedure also provides lower bounds on the optimal value. We present computational experiments showing that the proposed heuristics obtain high-quality solutions in modest CPU times.     

Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain

This paper addresses the solution of a two-stage stochastic programming model for an investment planning problem applied to the petroleum products supply chain. In this context, we present the development of acceleration techniques for the stochastic Benders decomposition that aim to strengthen the cuts generated, as well as to improve the quality of the solutions obtained during the execution of the algorithm. Computational experiments are presented for assessing the efficiency of the proposed framework. We compare the performance of the proposed algorithm with two other acceleration techniques. Results suggest that the proposed approach is able to efficiently solve the problem under consideration, achieving better performance in terms of computational times when compared to other two techniques.     

A Complete and Scalable Strategy for Coordinating Multiple Robots Within Roadmaps

This paper addresses the challenging problem of finding collision-free trajectories for many robots moving toward individual goals within a common environment. Most popular algorithms for multirobot planning manage the complexity of the problem by planning trajectories for robots individually; such decoupled methods are not guaranteed to find a solution if one exists. In contrast, this paper describes a multiphase approach to the planning problem that uses a graph and spanning tree representation to create and maintain obstacle-free paths through the environment for each robot to reach its goal. The resulting algorithm guarantees a solution for a well-defined number of robots in a common environment. The computational cost is shown to be scalable with complexity linear in the number of the robots, and demonstrated by solving the planning problem for 100 robots, simulated in an underground mine environment, in less than 1.5 s with a 1.5 GHz processor. The practicality of the algorithm is demonstrated in a real-world application requiring coordinated motion planning of multiple physical robots.