Search

In this paper, we investigate FRB, which is the single facility Euclidean location problem in the presence of a (non-)convex polygonal forbidden region where travel and location are not permitted. We search for a new facility’s location that minimizes the weighted Euclidean distances to existing ones. To overcome the non-convexity and non-differentiability of the problem’s objective function, we propose an equivalent reformulation (RFRB) whose objective is linear. Using RFRB, we limit the search space to regions of a set of non-overlapping candidate domains that may contain the optimum; thus we reduce RFRB to a finite series of tight mixed integer convex programming sub-problems. Each sub-problem has a linear objective function and both linear and quadratic constraints that are defined on a candidate domain. Based on these sub-problems, we propose an efficient bounding-based algorithm (BA) that converges to a (near-)optimum. Within BA, we use two lower and four upper bounds for the solution value of FRB. The two lower and two upper bounds are solution values of relaxations of the restricted problem. The third upper bound is the near-optimum of a nested partitioning heuristic. The fourth upper bound is the outcome of a divide and conquer technique that solves a smooth sub-problem for each sub-region. We reveal via our computational investigation that BA matches an existing upper bound and improves two more.

This paper considers the vehicle routing problem with multiple time windows. It introduces a general framework for three evolutionary heuristics that use three global multi-start strategies: ruin and recreate, genetic cross-over of best parents, and random restart. The proposed heuristics make use of information extracted from routes to guide customized data-driven local search operators. The paper reports comparative computational results for the three heuristics on benchmark instances and identifies the best one. It also shows more than 16% of average cost improvement over current practice on a set of real-life instances, with some solution costs improved by more than 30%.

In this study we propose a stochastic model that determines the number and type of surgeries to schedule in a two-week planning horizon where each operating session is assigned to a surgical specialty according to a fixed grid (Master Surgical Schedule). Our model considers surgery times, intensive care unit times and post-surgery lengths of stays stochastic and accounts for the availability of both intensive care unit beds and post-surgery beds. It aims to maximise the expected operating theatre’s throughput. The assignment problem, modelled as a stochastic problem, is solved via a sample average approximation. It gets an estimate of the optimum expected throughput for each specialty and of the operating theatre. We illustrate the application of the model on a real case study with real data from a leading European Children’s Hospital, study the sensitivity of obtained results to the two-week planned grid, and highlight the importance of considering the stochastic nature of the problem.

This paper considers the scheduling of preventive maintenance for the boilers, turbines, and distillers of power plants that produce electricity and desalinated water. It models the problem as a mathematical program (MP) that maximizes the sum of the minimal ratios of production to the demand of electricity and water during a planning time horizon. This objective encourages the plants’ production and enhances the chances of meeting consumers’ needs. It reduces the chance of power cuts and water shortages that may be caused by emergency disruptions of equipment on the network. To assess its performance and effectiveness, we test the MP on a real system consisting of 32 units and generate a preventive maintenance schedule for a time horizon of 52 weeks (one year). The generated schedule outperforms the schedule established by experts of the water plant, it induces, respectively, 16% and 12% increases in the surpluses while either matching or surpassing the total production. The sensitivity analysis further indicates that the generated schedule can handle unforeseen longer maintenance periods as well as a 120% increase in demand—a sizable realization in a country that heavily relies on electricity to acclimate to the harsh weather conditions. In addition, it suggests the robustness of the schedules with respect to increased demand. In summary, the MP model yields optimal systematic sustainable schedules.

The two-dimensional non-oriented bin packing problem with due dates packs a set of rectangular items, which may be rotated by 90°, into identical rectangular bins. The bins have equal processing times. An item’s lateness is the difference between its due date and the completion time of its bin. The problem packs all items without overlap as to minimize maximum lateness L max . The paper proposes a tight lower bound that enhances an existing bound on L max by 31.30% for 24.07% of the benchmark instances and matches it in 30.87% cases. Moreover, it models the problem via mixed integer programming (MIP), and solves small-sized instances exactly using CPLEX . It approximately solves larger-sized instances using a two-stage heuristic. The first stage constructs an initial solution via a first-fit heuristic that applies an iterative constraint programming (CP)-based neighborhood search. The second stage, which is iterative too, approximately solves a series of assignment low-level MIPs that are guided by feasibility constraints . It then enhances the solution via a high-level random local search. The approximate approach improves existing upper bounds by 27.45% on average, and obtains the optimum for 33.93% of the instances. Overall, the exact and approximate approaches find the optimum in 39.07% cases. The proposed approach is applicable to complex problems. It applies CP and MIP sequentially, while exploring their advantages, and hybridizes heuristic search with MIP. It embeds a new lookahead strategy that guards against infeasible search directions and constrains the search to improving directions only; thus, differs from traditional lookahead beam searches.

In this article, we focus on the conflict among the manager, the controller and the board of directors of a company. We model the problem as a three-player polymatrix game. Under a set of assumptions, we identify five potential Nash equilibria. We prove that the Nash equilibrium is unique, despite its changing structure. Next, we analyze the influence of the manager’s and controller’s bonuses and penalties on the Nash equilibria. Finally, we explain how the manager and the controller may decrease or maintain their performance, when their bonuses or penalties increase.

This paper considers the on-time guillotine cutting of small rectangular items from large rectangular bins. Items assigned to a bin define the bins’ processing time. Consequently, an item inherits the completion time of its assigned bin. Any deviation of an item’s completion time from its due date causes either earliness or tardiness penalties. This just-in-time two-dimensional bin packing problem (JITBP) combines two difficult discrete optimization problems: Bin packing and total weighted earliness tardiness single machine scheduling. It is herein modeled as an integrated constraint program, augmented with two sets of logically redundant constraints that speed the search. The first set uses the concept of dual feasible functions. It focuses on bin packing feasibility. The second is the result of a linear program that schedules filled bins on a single machine. As an alternative to this integrated model, this paper proposes two decomposition cut-and-check approaches that define the master problem (MP) as a relaxation of JITBP where the items are reduced to dimensionless entities. They then reestablish the geometric feasibility of the MPs’ solutions by iteratively augmenting MP with Benders cuts generated from the subproblems. The two approaches are similar in concept except that one implements MP as a constraint program (CP) while the second implements it as a mixed-integer program (MIP). Because JITBP is computationally challenging, we test all approaches under a number of heuristic assumptions, which include a maximum runtime for the MIP and CP solvers. The results provide computational evidence that the integrated constraint programming approach performs relatively well, and outperforms the decomposition approach whose MP is a CP. However, both approaches are outperformed by the decomposition approach whose MP is a warm-started MIP.

This paper addresses the single machine weighted number of on-time jobs scheduling problem where the machine is unavailable during one or more maintenance periods and the jobs share a common due date. It models the problem as a binary multiple knapsack (MKP), and offers an alternative proof that the problem is NP-Complete in the strong sense. Subsequently, it shows that some large-sized instances can be solved exactly within less than a second using an off-the-shelf solver. For difficult instances, the paper proposes a variable neighborhood search based heuristic V that explores the MKP nature of the problem to determine near-optima. V is dotted with two mechanisms that speed its convergence toward near-global optima: a linked list data structure and a dynamic threshold acceptance criterion. Experimental results provide computational evidence of the efficiency and efficacy of V for benchmark MKP instances and for scheduling problems alike. It further discusses the robustness of V with respect to the initial solution and problem's parameters. Highlights 1 , h k | nr - a , dj = d | Σ w i U i : a 0 / 1 multiple knapsack.Alternative proof that this scheduling problem is NP-Complete in the strong sense.Large-sized easy instances solved within less than a second.A variable neighborhood search with linked data structure/threshold acceptance.Results show good performance/robustness, and what constitutes a difficult instance.

This paper addresses the minimal makespan parallel machine problem where machines are subject to preventive maintenance events of a known deterministic duration. The processing time of a job depends on its predecessors since the machine’s last maintenance. The paper proposes some dominance criteria for sequences of jobs assigned to a machine, and uses these criteria to design constructive heuristics to this NP-hard problem. The computational investigation determines the parameters that make a hard instance and studies the sensitivity of the heuristics to these parameters.

This paper treats a discrete-time, two-item, stationary, infinite-horizon, stochastic inventory model. The system is reviewed at the beginning of each period where the inventory manager has the option of not ordering or ordering item 1 or item 2 or ordering jointly both items. If an order is made, then a set-up cost that depends on the ordered item(s) is accordingly incurred. The demand of each item in each period follows a known random distribution. In addition, the demands of the items are independent of each other and of the period. Inventory holding or backlogging costs are incurred depending on the stock level. This paper proposes and implements an exact stochastic dynamic program that determines the optimal steady state inventory policy. It exemplifies the form of the optimal policy for a number of demand distributions. This form turns out to be an extended (s, S) policy, where the state R 2 of possible inventory levels is naturally partitioned into two non overlapping sets: a stopping set and a continuation set. The stopping set consists of three non-overlapping subsets. The first corresponds to ordering item 1, the second to ordering item 2, and the third to jointly ordering items 1 and 2. In the continuation set, no action is required. The paper further illustrates the behavior of this policy for some interesting limiting cases, and discusses its sensitivity to the problem’s parameters.

Single-machine weighted earliness tardiness scheduling is a prevalent problem in just-in-time production environments. Yet, the case with distinct due dates is strongly NP-hard. Herein, it is approximately solved using ASV, an ant colony-based system with a reduced number of ants and of colonies and with daemon actions that explore the search space around the ants using a variable neighborhood search (VNS). The numerical investigation provides computational proof of the utility of the daemon actions. In addition, it infers that these latter can be applied either to the initial or to subsequent colonies. Furthermore, it highlights the importance of using ant colony optimization as the multiple restart engine of VNS. Finally, it shows that ASV obtains the optimum for most small-sized instances. It has a 0.2 % average deviation from the optimum over all benchmark instances.

The Vehicle Routing Problem (VRP) is a known optimization problems falling under the category of NP-Hard set of problems. VRP, along with its variations, continue to be extensively explored by the research community due to their large domain of application (environment, agriculture, industry, etc.) and economic impact on improving the overall performance, Quality of Services and reducing the operational cost. In this paper, we focus on VRPMTW; a variant of VRP with Multiple Time Windows constraints. We introduce a novel Hybrid Genetic Variable Neighborhood Search (HGVNS) based heuristic for the optimization of VRPMTW. The proposed framework uses genetic cross-over operators on a list of best parents and new implementations of local search operators. Computational results on benchmark data show substantial performance improvement when using the newly introduced heuristic.

This paper introduces and approximately solves a multi-component problem where small rectangular items are produced from large rectangular bins via guillotine cuts. An item is characterized by its width, height, due date, and earliness and tardiness penalties per unit time. Each item induces a cost that is proportional to its earliness and tardiness. Items cut from the same bin form a batch, whose processing and completion times depend on its assigned items. The items of a batch have the completion time of their bin. The objective is to find a cutting plan that minimizes the weighted sum of earliness and tardiness penalties. We address this problem via a constraint programming based heuristic (CP) and an agent based modelling heuristic (AB). CP is an impact-based search strategy, implemented in the general-purpose solver IBM CP Optimizer. AB is constructive. It builds a solution through repeated negotiations between the set of agents representing the items and the set representing the bins. The agents cooperate to minimize the weighted earliness-tardiness penalties. The computational investigation shows that CP outperforms AB on small-sized instances while the opposite prevails for larger instances.

Cut order planning (COP) is an NP-hard nonlinear optimization problem. Managers of apparel manufacturing units face this problem during the planning of the first stage of the manufacturing process. It affects the fluidity of the work flow and use of fabric. It consists in dividing every garment's order into sections, assigning the sizes to them, and determining their lengths and numbers of layers such that the total fabric length is minimized. Current industrial practice assumes that the length of the layout of a section is known a priori, and it does not depend on its combination of sizes. That is, the industry solves COP independently of the two-dimensional layout (TDL) that is the second stage of the manufacturing process. By relying on the length estimates in lieu of determining the actual length of a section, the industry is obtaining erroneous estimates of the true length used. Herein, COP and TDL are combined into a single problem CT (CT = COP + TDL) whose objective is to minimize fabric length. CT is solved using constructive heuristics, and three metaheuristics: a stochastic local improvement method, global improvement method, and hybrid approach. The approaches are tested on existing benchmark instances and new industrial cases. Their results provide computational proof of the benefits that industry can ripe by combining COP and TDL. The comparison of the performance of the approaches highlights their respective academic and practical utilities.

This paper presents a hybrid tabu search variable neighborhood (HVNTS) heuristic that chooses Pareto non-dominated solutions from the search space of solutions that satisfy a set of Nash equilibrium conditions for a multiple-agent game theory model. The framework is general and can tackle different classes of Vehicle Routing Problems (VRP). It is herein applied to the VRP with Multiple Time Windows (VRPMTW) and tested on three objectives: minimizing the total travel cost (expressed in time units), maximizing the minimal customers' utility, and maximizing the minimal drivers' utility. The results for benchmark instances highlight the benefits of the multiple-criteria model; an important motivation to the transportation industry for its real life implementation.

The circular packing problem (CPP) consists of packing n circles C i of known radii r i , i∈N={1, …, n}, into the smallest containing circle ℂ. The objective is to determine the coordinates (x i , y i ) of the centre of C i , i∈N, as well as the radius r and centre (x, y) of ℂ. CPP, which is a variant of the two-dimensional open-dimension problem, is NP hard. This paper presents an adaptive algorithm that incorporates nested partitioning within a tabu search and applies some diversification strategies to obtain a (near) global optimum. The tabu search is to identify the n circles’ ordering, whereas the nested partitioning is to determine the n circles’ positions that yield the smallest r. The computational results show the efficiency of the proposed algorithm.

ED EPS; International audience; This paper solves FC_2TDC, the two-staged fixed-orientation two-dimensional cutting stock problem. FC_2TDC is a variant of the constrained two-dimensional cutting problem where each piece is produced, in the final cutting pattern, by at most two cuts, and each piece has a fixed orientation. It is solved by an algorithm that combines a strip-generation procedure with beam search (BS). BS, which is a truncated branch-and-bound, investigates a subset of elite nodes and permanently fathoms the others. It chooses the elite nodes based on an evaluation operator. The importance of the evaluation operator on the performance of BS is highlighted by comparing a local beam search (LBS) that uses a priority cost-evaluation operator to a global beam search (GBS) that adopts a global cost-evaluation operator. Computational results, based on several medium and large instances, further show that LBS provides good solutions, whereas GBS gives (near) optimal solutions within reasonable computational time.

International audience; This paper studies the circular packing problem (CPP) which consists of packing n non-identical circles Ci of known radius ri, i N = {1, ... , n}, into the smallest containing circle C. The objective is to determine the coordinates (xi, yi) of the center of Ci, i N, as well as the radius r and center (x, y) of C. This problem, which is a variant of the two-dimensional open dimension problem, is solved using a two-step, dynamic, adaptive, local search algorithm. At each iteration, the algorithm identifies the set of potential "best local positions" of a circle Ci, i N, given the positions of the previously packed circles, and determines for each of these positions the coordinates and radius of the smallest containing circle. The "best local position" minimizes the radius of the current containing circle. That is, every time an additional circle is packed, both the center and the radius of the containing circle are dynamically updated, and the smallest containing circle is known. The experimental results reflect the good performance of the algorithm.

International audience; In this paper, we propose to solve the circular packing problem (CPP) whose objective is to pack n different circles Ci of known radius View the MathML source, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (xi,yi) of the center of the packed circles View the MathML source. CPP is solved by using an adaptive beam search algorithm that combines the beam search, the local position distance and the dichotomous search strategy. Decisions at each node of the developed tree are based on the well-known maximum hole degree that uses the local minimum distance. The computational results, on a set of instances taken from the literature, show the effectiveness of the proposed algorithm.

ED EPS; International audience; In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.

International audience; In this paper, we study the circular packing problem (CPP) which consists of packing a set of non-identical circles of known radii into the smallest circle with no overlap of any pair of circles. To solve CPP, we propose a three-phase approximate algorithm. During its first phase, the algorithm successively packs the ordered set of circles. It searches for each circle's "best" position given the positions of the already packed circles where the best position minimizes the radius of the current containing circle. During its second phase, the algorithm tries to reduce the radius of the containing circle by applying (i) an intensified search, based on a reduction search interval, and (ii) a diversified search, based on the application of a number of layout techniques. Finally, during its third phase, the algorithm introduces a restarting procedure that explores the neighborhood of the current solution in search for a better ordering of the circles. The performance of the proposed algorithm is evaluated on several problem instances taken from the literature.

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W , as to maximize the sum of the profits of the pieces to be cut. Each piece type i , i = 1, …, n , is characterized by a length l i , a width w i , a profit (or weight) c i and an upper demand value b i . The upper demand value is the maximum number of pieces of type i which can be cut on rectangle ( L , W ). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure . We evaluate the performance of these algorithms on instances extracted from the literature.

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate S with length L and width W, to maximize the sum of the profits of the pieces to be cut. Each piece type i, i=1,…,n, is characterized by a length li, a width wi, a profit (or weight) ci, and an upper demand value bi. The upper demand value is the maximum number of pieces of type i that can be cut on S. In this paper, we study the two-staged C_TDC problem, noted C_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two cuts. We solve the C_2TDC problem using an exact algorithm that is mainly based on a bottom-up strategy. We introduce new lower and upper bounds and propose new strategies that eliminate several duplicate patterns. We evaluate the performance of the proposed exact algorithm on problem instances extracted from the literature and compare it to the performance of an existing exact algorithm.