An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem

We consider a resource‐constrained project scheduling problem originating in particle therapy for cancer treatment, in which the scheduling has to be done in high resolution. Traditional mixed integer linear programming techniques such as time‐indexed formulations or discrete‐event formulations are known to have severe limitations in such cases, that is, growing too fast or having weak linear programming relaxations. We suggest a relaxation based on partitioning time into so‐called time‐buckets. This relaxation is iteratively solved and serves as basis for deriving feasible solutions using heuristics. Based on these primal and dual solutions and bounds, the time‐buckets are successively refined. Combining these parts, we obtain an algorithm that provides good approximate solutions soon and eventually converges to an optimal solution. Diverse strategies for performing the time‐bucket refinement are investigated. The approach shows excellent performance in comparison to the traditional formulations and a metaheuristic.     

Hybrid approach for the two‐dimensional bin packing problem with two‐staged patterns

This paper presents a two‐phase heuristic approach for the two‐dimensional bin packing problem with two‐staged patterns and nonoriented items. A solution is generated in each phase and the better one is selected. Residual problems are solved by column generation in the first phase, where a partial admitting procedure is used to admit some of the patterns into the phase‐1 solution. The second solution is obtained from solving an integer linear programming problem over the set of all patterns generated in the first phase, where a time limit is used and subsequently the solution may not be optimal over the pattern set. The computational results indicate that the approach yields the best solution quality among the heuristics that use two‐staged or more complex patterns.     

A note on approximating the min–max vertex disjoint paths on directed acyclic graphs

This paper shows that the FPTAS for the min–max disjoint paths problem on directed acyclic graphs by Yu et al. (2010) [7] can be improved by a rounding and searching technique.     

Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization

In the two‐dimensional (2D) cutting (2DC) problem, a large rectangular sheet has to be dissected into smaller rectangular pieces with the aim of maximizing the total profit associated with the extracted pieces. When the number of copies of each piece to be extracted is bounded, it is referred to as constrained 2DC (C2DC) problem. The C2DC has been widely studied by the operations research community for its applications and theoretical issues. In this work, we recall the best exact and heuristic solving approaches for the C2DC and we provide a review and a categorization of the available upper bounds. We also discuss improvements and combinations of these upper bounds and give directions for their effective exploitation. Finally, we demonstrate the loss of accuracy of several exact methods present in literature because of the effect of the used antiredundancy strategies on the implemented bounding criteria. This work, based on more than 90 contributions, has a twofold target. For researchers working in C2DC, it provides a useful insight on the topic. For expert practitioners, it represents a systematic collection of the main findings and achievements, posing also the basis for future research.     

Reduction in the number of binary variables for inter‐sample avoidance in trajectory optimizers using mixed‐integer linear programming

This note proposes the use of a tuple encoding scheme to reduce the number of binary variables involved in trajectory optimization problems with inter‐sample avoidance constraints. Copyright © 2016 John Wiley & Sons, Ltd.     

Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

In this paper, we address the constrained two‐dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts. In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider only two‐staged or one‐group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch‐and‐Benders‐cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the object's dimensions.     

Hybrid approaches for the two‐scenario max–min knapsack problem

In this paper, we deal with the two‐scenario max–min knapsack (MNK) problem. First, we consider several formulations of MNK as a mixed integer programming problem. Then, we propose a hybrid method as an alternative to solve the MNK exactly. The approach combines relaxation technique and the temporary setting of variables to improve iteratively two sequences of upper and lower bounds. More precisely, pseudo‐cuts are added to the problem to strengthen the bounds and reduce the gap between the best lower bound and the best upper bound. The algorithm stops when the proof of the optimality of the best solution is found. We also use a reduction technique to set some variables definitively at their optimal values. Numerical experiments demonstrate the robustness of the approach. In particular, our algorithm is efficient to solve large and correlated instances of MNK.     

Inter‐sample avoidance in trajectory optimizers using mixed‐integer linear programming

This paper proposes an extension to trajectory optimization using mixed‐integer linear programming. The purpose of the extension is to ensure that avoidance constraints are respected at all times between discrete samples, not just at the sampling times themselves. The method is very simple and involves applying the same switched constraints at adjacent time steps. This requires fewer additional constraints than the existing approach and is shown to reduce computation time. A key benefit of efficient inter‐sample avoidance is the facility to reduce the number of time steps without having to compensate by enlarging the obstacles. A further extension to the principle is presented to account for curved paths between samples, proving useful in cases where narrow passageways are traversed. Copyright © 2013 John Wiley & Sons, Ltd.     

Solving the bi‐objective capacitated p‐median problem with multilevel capacities using compromise programming and VNS

A bi‐objective optimisation using a compromise programming (CP) approach is proposed for the capacitated p‐median problem (CPMP) in the presence of the fixed cost of opening facility and several possible capacities that can be used by potential facilities. As the sum of distances between customers and their facilities and the total fixed cost for opening facilities are important aspects, the model is proposed to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal location of open facilities with their optimal capacity. Two approaches are designed to deal with the bi‐objective CPMP, namely CP with an exact method and with a variable neighbourhood search (VNS) based matheuristic. New sets of generated instances are used to evaluate the performance of the proposed approaches. The computational experiments show that the proposed approaches produce interesting results.     

Agile optimization of a two‐echelon vehicle routing problem with pickup and delivery

In this paper, we consider a vehicle routing problem in which a fleet of homogeneous vehicles, initially located at a depot, has to satisfy customers' demands in a two‐echelon network: first, the vehicles have to visit intermediate nodes (e.g., a retail center or a consolidation center), where they deliver raw materials or bulk products and collect a number of processed items requested by the customers in their route; then, the vehicles proceed to complete their assigned routes, thus delivering the processed items to the final customers before returning to the depot. During this stage, vehicles might visit other intermediate nodes for reloading new items. In some real‐life scenarios, this problem needs to be solved in just a few seconds or even milliseconds, which leads to the concept of “agile optimization.” This might be the case in some rescue operations using drones in humanitarian logistics, where every second can be decisive to save lives. In order to deal with this real‐time two‐echelon vehicle routing problem with pickup and delivery, an original constructive heuristic is proposed. This heuristic is able to provide a feasible and reasonably good solution in just a few milliseconds. The constructive heuristic is extended into a biased‐randomized algorithm using a skewed probability distribution to modify its greedy behavior. This way, parallel runs of the algorithm are able to generate even better results without violating the real‐time constraint. Results show that the proposed methodology generates competitive results in milliseconds, being able to outperform other heuristics from the literature.     

A practical three‐phase ILP approach for solving the examination timetabling problem

A practical mathematical programming based approach is introduced for solving the examination timetabling problem at the German Jordanian University (GJU), whereby the complex process of acquiring a feasible examination timetable is simplified by subdividing it into three smaller sub‐problems (phases). Accordingly, the exams are initially allocated to time slots in phase one, the time slots are then allotted to days in phase two, and finally in phase three the exams are assigned to rooms based on the number of students taking each exam and capacities of the rooms. The solution for each phase is acquired based on an integer linear programming (ILP) formulation, while satisfying a set of hard constraints that ensure comfortable exam timetables for all students and meet the desired requirements set by GJU administrative staff. Furthermore, the solver can be controlled and launched from a student information system named MyGJU Admin, which enabled registrars at the university to easily, quickly, and accurately generate final exam timetables in several standard formats. Moreover, the approach was validated based on recent GJU registration information as well as real‐world benchmark data.     

Solving a timetabling problem using hybrid genetic algorithms

All over the world, human resources are used on all kinds of different scheduling problems, many of which are time-consuming and tedious. Scheduling tools are thus very welcome. This paper presents a research project, where Genetic Algorithms (GAs) are used as the basis for solving a timetabling problem concerning medical doctors attached to an emergency service. All the doctors express personal preferences, thereby making the scheduling rather difficult. In its natural form, the timetabling problem for the emergency service is stated as a number of constraints to be fulfilled. For this reason, it was decided to compare the strength of a Co-evolutionary Constraint Satisfaction (CCS) technique with that of two other GA approaches. Distributed GAs and a simple special-purpose hill climber were introduced, to improve the performance of the three algorithms. Finally, the performance of the GAs was compared with that of some standard, nonGA approaches. The distributed hybrid GAs were by far the most successful, and one of these hybrid algorithms is currently used for solving the timetabling problem at the emergency service. © 1997 John Wiley & Sons, Ltd.     

MRMOGA: a new parallel multi‐objective evolutionary algorithm based on the use of multiple resolutions

In this paper, we introduce MRMOGA (Multiple Resolution Multi‐Objective Genetic Algorithm), a new parallel multi‐objective evolutionary algorithm which is based on an injection island approach. This approach is characterized by adopting an encoding of solutions which uses a different resolution for each island. This approach allows us to divide the decision variable space into well‐defined overlapped regions to achieve an efficient use of multiple processors. Also, this approach guarantees that the processors only generate solutions within their assigned region. In order to assess the performance of our proposed approach, we compare it to a parallel version of an algorithm that is representative of the state‐of‐the‐art in the area, using standard test functions and performance measures reported in the specialized literature. Our results indicate that our proposed approach is a viable alternative to solve multi‐objective optimization problems in parallel, particularly when dealing with large search spaces. Copyright © 2006 John Wiley & Sons, Ltd.     

Inclusion,subsumption, JJ‐paths,and structured path testing: a Redress

Introduced in 1976 by Hennell, Woodward, and Hedley, the Linear Code Sequence and Jump (LCSAJ) has since been named the jump‐to‐jump path (JJ‐path). If all JJ‐paths in a piece of code have been tested, then it is guaranteed, for example, that all of the code's branches and all of its statements will likewise have been tested. JJ‐path testing is thus said to include both branch and statement testing. Over the years, much work has been carried out on the inclusion relation, and this is also true of a closely‐linked relation that is known as subsumption. Not surprisingly, some of the work in the literature has focussed on the criteria of executing all JJ‐paths and sequences of such, and how these criteria relate to other path coverage and test data criteria. Unfortunately, certain results involving JJ‐paths in the context of inclusion, as portrayed in a widely referenced and influential paper, are in error. Consequently, the main purpose of this paper is to rectify this situation. Copyright © 2008 John Wiley & Sons, Ltd.     

Evolutionary algorithms for the multi‐objective test data generation problem

Automatic test data generation is a very popular domain in the field of search‐based software engineering. Traditionally, the main goal has been to maximize coverage. However, other objectives can be defined, such as the oracle cost, which is the cost of executing the entire test suite and the cost of checking the system behavior. Indeed, in very large software systems, the cost spent to test the system can be an issue, and then it makes sense by considering two conflicting objectives: maximizing the coverage and minimizing the oracle cost. This is what we did in this paper. We mainly compared two approaches to deal with the multi‐objective test data generation problem: a direct multi‐objective approach and a combination of a mono‐objective algorithm together with multi‐objective test case selection optimization. Concretely, in this work, we used four state‐of‐the‐art multi‐objective algorithms and two mono‐objective evolutionary algorithms followed by a multi‐objective test case selection based on Pareto efficiency. The experimental analysis compares these techniques on two different benchmarks. The first one is composed of 800 Java programs created through a program generator. The second benchmark is composed of 13 real programs extracted from the literature. In the direct multi‐objective approach, the results indicate that the oracle cost can be properly optimized; however, the full branch coverage of the system poses a great challenge. Regarding the mono‐objective algorithms, although they need a second phase of test case selection for reducing the oracle cost, they are very effective in maximizing the branch coverage. Copyright © 2011 John Wiley & Sons, Ltd.     

An evolutionary algorithm for the one‐dimensional cutting stock problem

This paper deals with the one‐dimensional integer cutting stock problem, which consists of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to minimize the waste of material. The case in which there are various types of objects available in stock in limited quantities is studied. A new heuristic method based on the evolutionary algorithm concept is proposed to solve the problem. This heuristic is empirically analyzed by solving randomly generated instances and the results are compared with other methods from the literature.     

Integer linear programming for a cutting problem in the wood-processing industry: a case study

In this paper, the authors present a case study from the wood-processing industry. It focuses on a cutting process in which material from stock is cut down in order to provide the items required by the customers in the desired qualities, sizes, and quantities. In particular, two aspects make this cutting process special. Firstly, the cutting process is strongly interdependent, with a preceding handling process, which, consequently, cannot be planned independently. Secondly, if the trim loss is of a certain minimum size, it can be returned into stock and used as input to subsequent cutting processes. In order to reduce the cost of the cutting process, a decision support tool has been developed that incorporates an integer linear programming model as a central feature. The model is described in detail, and experience from the application of the tool is reported.     

A simulated annealing with multiple‐search paths and parallel computation for a comprehensive flowshop scheduling problem

Recent studies have demonstrated that the performance of a simulated annealing algorithm can be improved by following multiple‐search paths and parallel computation. In this paper, we use these strategies to solve a comprehensive mathematical model for a flexible flowshop lot streaming problem. In the flexible flowshop environment, a number of jobs will be processed in several consecutive production stages, and each stage may involve a certain number of parallel machines that may not be identical. Each job has to be split into several unequal sublots by following the concept of lot streaming. The sublots are to be processed in the order of the stages, and sublots of certain products may skip some stages. This complex problem also incorporates sequence‐dependent setup times, the anticipatory or nonanticipatory nature of setups, release dates for machines, and machine eligibility. Numerical examples are presented to demonstrate the effectiveness of lot streaming in hybrid flowshops, the performance of the proposed simulated annealing algorithm, and the improvements achieved using parallel computation.     

Reduced‐cost microwave filter modeling using a two‐stage Gaussian process regression approach

A technique for the reduced‐cost modeling of microwave filters is presented. Our approach exploits variable‐fidelity electromagnetic (EM) simulations, and Gaussian process regression (GPR) carried out in two stages. In the first stage of the modeling process, a mapping between EM simulation filter models of low and high fidelity is established. The mapping is subsequently used in the second stage, making it possible for the final surrogate model to be constructed from training data obtained using only a fraction of the number of high‐fidelity simulations normally required. As demonstrated using three examples of microstrip filters, the proposed technique allows us to reduce substantially (by up to 80%) the central processing unit (CPU) cost of the filter model setup, as compared to conventional (single‐stage) GPR—the benchmark modeling method in this study. This is achieved without degrading the model generalization capability. The reliability of the two‐stage modeling method is demonstrated through the successful application of the surrogates to surrogate‐based filter design optimization. © 2014 Wiley Periodicals, Inc. Int J RF and Microwave CAE 25:453–462, 2015.     

Enhanced genetic algorithms for a bi‐objective bus driver rostering problem: a computational study

In this work, the bus driver rostering problem is considered in the context of a noncyclic rostering, with two objectives representing either the company or the drivers’ interests. A network model and a proof of the NP‐hardness of the problem are presented, along with a bi‐objective memetic algorithm that combines a specific decoder with a utopian/lexicographic elitism, a strength Pareto fitness evaluation, and a local search procedure. By taking real and benchmark instances the computational behavior of the memetic algorithm is compared with simpler versions to assess the effects of the embedded components. The developed algorithm is a valuable tool for bus companies’ planning departments insofar as it yields at low computing times a pool of good quality rosters that reconcile contradictory objectives. This study shows that simple enhancements in standard bi‐objective genetic algorithms may improve the results for this difficult combinatorial problem.