Search

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.

This chapter proposes a new research direction whose viability is due to advances of computing technologies. It combines mixed integer and constraint programming in different ways in quest of effective search techniques. It uses exact approaches as approximate ones not only by imposing runtime and bounding limits, but also by relaxing the mathematical models in a non-classical way. For example, it augments the model with “non-traditional constraints,” substitutes hard constraints with “easier” ones, and limits the search space to neighborhoods that may contain the optimum. The resulting search techniques offer industries a competitive edge by identifying near-optimal solutions to complex problems and providing them, at no investment cost, with feasible/directly implementable solutions to realistic instances (not to their abstract/simplified form). This chapter illustrates such benefits on a very difficult industrial engineering problem: vehicle routing with multiple time windows. This problem has a compounded difficulty. It involves two NP-hard subproblems: routing and scheduling. Solving its real-life instances is almost impossible. However, good quality solutions may be obtained in reasonable times via the proposed technique.

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.

The D-minimax criterion for estimating slopes of a response surface involving k factors is considered for situations where the experimental region χ and the region of interest ℜ are co-centered cubes but not necessarily identical. Taking χ = [ − 1, 1]k and ℜ = [ − R, R]k, optimal designs under the criterion for the full second-order model are derived for various values of R and their relative performances investigated. The asymptotically optimal design as R → ∞ is also derived and investigated. In addition, the optimal designs within the class of product designs are obtained. In the asymptotic case it is found that the optimal product design is given by a solution of a cubic equation that reduces to a quadratic equation for k = 3 and 6. Relative performances of various designs obtained are examined. In particular, the optimal asymptotic product design and the traditional D-optimal design are compared and it is found that the former performs very well.

This paper addresses the problem of scheduling on-time jobs on unrelated parallel machines with machine production costs. The objective is to maximise the net profit which is the sum of the weights of on-time jobs and the cost of using the machines. This scheduling problem is very important and frequent in industrial settings. It is herein solved using an exact approach that applies Benders decomposition to obtain tight upper and lower bounds and uses the bounds within a branch and bound. The computational investigation shows the efficacy of the approach in solving large instances. Most importantly, the proposed approach provides a new venue for solving large-scale scheduling problems.

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.

This paper considers the minimal earliness tardiness -machine permutation flow shop scheduling problem with distinct due dates and no inserted idle time when a job is waiting. It models the problem as a mixed integer program, and approximately solves it using , a fast variable neighborhood based hybrid heuristic. is an iterated local search that applies a variable neighborhood descent as its search engine. The numerical testing provides computational proof of the good performance of , which matches existing upper bounds of 20.02% benchmark instances and tightens 70.54% ones with an average percent deviation from the best upper bound of 0.07%.

This paper demonstrates the ease and invaluable benefits of applying simple Operations Research (OR) tools to a common and sensitive problem in health care. Specifically, it investigates the problem of designing timetables for nurses working in Kuwaiti health care units that operate around the clock. It details the constraints of the problem, specifies the objective, proposes a mixed integer program, solves the mathematical model for the case of a specific health care unit using an off-the-shelf optimizer, and explains how the model can account for other real life context-dependent constraints. The computational investigation demonstrates the simplicity of automatically generating timetables that have four to five-week review periods and any lead times. In addition, it proves the superiority of the obtained timetables to those generated manually by the head nurse, and proves the feasibility of taking into consideration the nurses’ requests for duty and rest shifts. Moreover, it illustrates the applicability of the model to a hospital ward where a variety of special constraints such as historical data and vacations are in vigor. Generating the timetables using the proposed model contributes to improving the level of satisfaction of nurses and to enhancing their job performance; subsequently, it offers a safer environment for patients. Finally, the paper underscores the benefits of popularizing OR in the health care sector. An appropriate knowledge of OR enables health care personnel to solve vital problems independently and efficiently.

Scheduling jobs with different processing times and distinct known due dates on parallel machines (which may be idle) so as to minimise the total weighted earliness and tardiness is NP-hard. It occurs frequently in industrial settings with a just-in-time production environment. Here, small instances of this problem are tackled via an exact mixed-integer program, whereas larger instances are approximately solved using hybrid algorithms. The computational investigation discerns what makes a difficult instance, and demonstrates the efficiency of the approach.

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.

In this paper, we describe an exact algorithm to solve the weighted number of tardy jobs two-machine flow shop scheduling problem. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate problems with 100 jobs can be solved quickly.

The two-dimensional layout (TDL) optimization problem consists of finding the minimal length layout of a set of both regular and irregular two-dimensional shapes on a stock sheet of finite width but infinite length. The layout should not contain any overlap. In this paper, we solve the TDL problem by proposing two approximate algorithms. The first one is a new heuristic based on a constructive approach specifically designed for irregular shapes, but that works well with regular ones. The second is a hybrid method in which the constructive approach displays the layouts corresponding to the chromosomes yielded by the genetic algorithm. The resulting algorithm yields satisfactory results in relatively short computational times as shown by the extensive computational testing on problems from the literature.

In this paper, we describe an exact algorithm to solve the single machine weighted number of tardy jobs scheduling problem. The algorithm uses branch-and-bound with the bounds obtained from a surrogate knapsack. Extensive computational experiments are carried out. These experiments validate previous work on what constitutes a difficult instance and show that even difficult instances with 2500 jobs can be solved optimally in a reasonable amount of time.

This paper addresses the circular packing problem (CPP) which consists in packing n circles C i , each of known radius r i , i∈N={1,…,n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x i , y i ) of each circle C i . This problem is solved via a binary search that evaluates the solution using a non-oscillating beam search with separate beams (instead of pooled ones). This beam search guarantees a monotonic decrease of r as the beam width increases. A node of level l of the beam search tree represents a partial packing of l circles into C. The potential of each node of the tree is assessed via a look-ahead strategy. The computational results on different benchmark instances show the effectiveness 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.

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.

International audience; Learning agents have to deal with the exploration-exploitation dilemma. The choice between exploration and exploitation is very difficult in dynamic systems; in particular in large scale ones such as economic systems. Recent research shows that there is neither an optimal nor a unique solution for this problem. In this paper, we propose an adaptive approach based on meta-rules to adapt the choice between exploration and exploitation. This new adaptive approach relies on the variations of the performance of the agents. To validate the approach, we apply it to economic systems and compare it to two adaptive methods originally proposed by Wilson: one local and one global. Moreover, we compare different exploration strategies and focus on their influence on the performance of the agents.

International audience; Learning agents have to deal with the exploration-exploitation dilemma. The choice between exploration and exploitation is very difficult in dynamic systems; in particular in large scale ones such as economic systems. Recent research shows that there is neither an optimal nor a unique solution for this problem. In this paper, we propose an adaptive approach based on meta-rules to adapt the choice between exploration and exploitation. This new adaptive approach relies on the variations of the performance of the agents. To validate the approach, we apply it to economic systems and compare it to two adaptive methods: one local and one global. Herein, we adapt these two methods, which were originally proposed by Wilson, to economic systems. Moreover, we compare different exploration strategies and focus on their influence on the performance of the agents.

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.

A new adaptive economic control scheme for a fuzzy quality characteristic is introduced in this paper. The control scheme includes a sampling interval, a sample size, and an action that are all variable. It minimises the total cost of a multistage process over a short production run. The state of the process is described via a membership function and the aggregate fuzzy membership function of the sample is used instead of commonly used measures of centrality. This scheme, originally designed for an actual industrial case, can be applied to a variety of manufacturing processes where the quality characteristic of interest is fuzzy or where the sampling outcome is expressed via linguistic variables. Extensive computational results show that it brings about sizeable savings. In particular, it is less costly than schemes where the static control limits are based on the fuzzy mean deviation and two-way classification economic adaptive control schemes.

This article studies the circular packing problem (CPP) which consists of packing n circles of known radii into the smallest containing circle C. The objective is to determine the coordinates of the centres of the circles as well as the radius of C. CPP, which is a variant of the 2D open-dimension problem, embeds two extremely difficult problems: a pure continuous optimisation problem and a combinatorial one. This article provides experimental proof that the continuous and combinatorial aspects of the problem should not be tackled independently, and need to be considered simultaneously. Specifically, it proposes two beam search algorithms. The first algorithm is a two-stage approach. Stage one uses a filtered beam search to identify the best ordering of the circles whereas stage two uses a recovering beam search along with non-linear optimisation to find the best position of each circle given the ordering identified during stage one. The second algorithm embeds both searches into a single search tree where each level has two sublevels: sublevel one applies a filtered beam search to identify the circle to be packed whereas sublevel two applies a recovering beam search along with non-linear optimisation to identify its position. The computational results further show that the second algorithm obtains very good results.

A two-stage Hybrid Flowshop Problem (FS"m"""1"," "m"""2) is a two-center shop with several parallel machines per center and n jobs to be processed on at most one machine per center. The objective consists of minimizing the maximum completion time. Two two-phase methods based on Simulated Annealing and Tabu Search are proposed. The results are compared with solutions provided by existing heuristics, and with a new derived lower bound. These comparisons show the superiority of the derived lower bound and the efficiency of the proposed heuristic. The Tabu search based heuristic yields the optimal solution for 35% of the problems. Its average relative error is 0.82%.