Search

Fine paper mills produce a variety of paper grades to satisfy demand for a large number of sheeted products. Huge reels of different paper grades are produced on a cyclical basis on paper machines. These reels are then cut into rolls of smaller size which are then either sold as such, or sheeted into finished products in converting plants. A huge number of roll sizes would be required to cut all finished products without trim loss and they cannot all be inventoried. An assortment of rolls is inventoried with the implication that the sheeting operations may yield trim loss. The selection of the assortment of roll sizes to stock and the assignment of these roll sizes to finished products have a significant impact on performances. This paper presents a model to decide the parent roll assortment and assignments to finished products based on these products demand processes, desired service levels, trim loss and inventory holding costs. Risk pooling economies made by assigning several finished products to a given roll size is a fundamental aspect of the problem. The overall model is a binary non-linear program. Two solution methods are developed: a branch and price algorithm based on column generation and a fast pricing heuristic, and a marginal cost heuristic. The two methods are tested on real data and also on randomly generated problem instances. The approach proposed was implemented by a large pulp and paper company.

This work describes a real-world industrial problem of production planning and cutting optimization of reels and sheets, occurring at a Portuguese paper mill. It will focus on a particular module of the global problem, which is concerned with the determination of the width combinations of the items involved in the planning process: the main goal consists in satisfying an order set of reels and sheets that must be cut from master reels. The width combination process will determine the quantity/weight of the master reels to be produced and their cutting patterns, in order to minimize waste, while satisfying production orders.A two-phase approach has been devised, naturally dependent on the technological process involved. Details of the models and solution methods are presented. Moreover some illustrative computational results are included.

In wireless ad-hoc networks, the broadcast scheduling problem (BSP) is commonly viewed as a well-known NP-complete combinatorial optimization problem. The purpose of the BSP is to achieve a transmission schedule with collision-free time slots in a time division multiple access ad-hoc network. The transmission schedule is optimized by minimizing the frame length of the node transmissions and maximizing the utilization of the shared channel. In this work, we propose a new evolutionary algorithm to solve the BSP by adopting the rock-paper-scissors dynamics found in natural systems. We use three types of species with strategies of different levels of intensification and diversification to simulate the rock-paper-scissors dynamics. Based on this evolutionary game, in which the success of one species relies on the behavior of others, the dynamic coexistence of three species can be achieved to control the balance between intensification and diversification. The experimental results demonstrate that our algorithm is efficient and effective at solving large instances of the BSP.

The purpose of this paper is to solve a multi-period garbage collection problem involving several garbage types called fractions, such as general and organic waste, paper and carboard, glass and metal, and plastic. The study is motivated by a real-life problem arising in Denmark. Because of the nature of the fractions, not all of them have the same collection frequency. Currently the collection days for the various fractions are uncoordinated. An interesting question is to determine the added cost in terms of traveled distance and vehicle fleet size of coordinating these collections in order to reduce the inconvenience borne by the citizens. To this end we develop a multi-phase heuristic: (1) small collection districts, each corresponding to a day of the week, are first created; (2) the districts are assigned to specific weekdays based on a closeness criterion; (3) they are balanced in order to make a more efficient use of the vehicles; (4) collection routes are then created for each district and each waste fraction by means of the FastCARP heuristic. Extensive tests over a variety of scenarios indicate that coordinating the collections yields a routing cost increase of 12.4%, while the number of vehicles increases in less than half of the instances.

In this paper, we present a new variant of the Clustered Orienteering Problem (COP) that we refer to as the Clustered Team Orienteering Problem (CluTOP). In this problem, customers are grouped into subsets called clusters. A profit is associated with each cluster and is gained only if all of its customers are served. A set of available vehicles with a limited travel time collaborates in order to visit the customers of the clusters. The objective is to maximize the total collected profit with respect to a travel time limit. The first contribution of this paper consists of an exact method based on a cutting planes approach. This method includes the consideration of a set of valid inequalities. In particular, an incompatibility-cluster-based valid inequality is proposed. Moreover, a pre-processing procedure is considered in order to compute the incompatibilities between clusters. The second contribution is a hybrid heuristic that combines an Adaptive Large Neighborhood Search (ALNS) and an effective split procedure. These two components cooperate together for the purpose of exploring both direct representation and giant tours search spaces. Experimental results show that the cutting planes based algorithm outperforms the state-of-the-art exact methods, in the particular case of a single vehicle by solving 61 additional instances. Moreover, the hybrid heuristic succeeds in finding 38 new best known solutions for the case of one vehicle. For the case with multiple vehicles, new benchmark instances are generated based on those introduced for the COP. Regarding the performance of the methods, the heuristic method finds the optimal solution for almost all the instances solved by the exact method.

In a cloud environment, the aim of using optimal resources can be achieved using a load-balancing technique. The load-balancing technique assigns a set of requests into a set of resources for distributing the load. It is one of the significant issues in cloud computing and known as an NP-hard problem. Therefore, many nature-inspired meta-heuristic techniques are proposed to provide high efficiency. However, despite the importance of the nature-inspired meta-heuristic techniques for solving the problem of the load-balancing in the cloud environment, there is not a complete and detailed paper about reviewing and studying the main important issues in this domain. Therefore, this paper presents comprehensive coverage of the nature-inspired meta-heuristic techniques applied in the area of the cloud load-balancing. The main goal of this paper is to highlight the emphasis on optimization algorithms and the benefits that they provide to overcome the cloud load-balancing challenges. In addition, to solve the load-balancing problem in the cloud environments, the advantages and disadvantage of the nature-inspired meta-heuristic algorithms have been analyzed and their significant challenges are considered for proposing the techniques that are more effective in the future.

This paper addresses the transportation of valuable goods in which security carriers are interested to optimize the operating costs and the vehicle routes’ security. In real operations, route planning and scheduling are normally performed manually based on individual experience. Hereupon, an optimizing approach should be developed to target the robbery risk reduction and the distribution network’ operational costs. Facing the dangerous nature of operations, some considerations play an important role, including demand fluctuations and traffic congestion of the urban environment. To handle these issues, we respectively benefit from the robust optimization theory and considering time-dependent travel speeds with satisfying the “first-in-first-out” property. This paper proposes a rich vehicle routing problem denoted by the secure time-dependent vehicle routing problem with time windows including pickup and delivery with uncertain demands (S-TD-VRPTWPD-UD). A mathematical formulation and an efficient solution approach combining the greedy randomized adaptive search procedure (GRASP) and the iterated local search (ILS) are developed to minimize the predictability of route plans using an integrated risk index, besides the travel costs. Extensive computational experiments on this problem are performed to analyze the impact of the demand uncertainty and the speed time-dependency and to show the efficiency of the GRASP × ILS implementation. The results show the significant improvements due to the time-dependency as well as the extra cost of protecting the model against the worst-case scenario of demand requests by deriving the robust counterpart of the S-TD-VRPTWPD-UD.

This paper concentrates on a capacitated multi-period cutting stock problem. In the production process, multiple identical input rods can be bundled together and cut simultaneously. We say that these input rods are cut with the same pattern. Vanderbeck (2000) once noted that changing from one pattern to another involves significant setup times (to adjust for knife positions) and costs (e.g., those associated with waste from trial runs); thus, the pattern setup cost cannot be neglected. In this paper, we therefore consider the capacitated multi-period cutting stock problem with pattern setup cost. In this regard, we aim to determine the patterns and occurrence of such patterns in each decision period over the planning horizon in order to minimize the total cost, including the pattern setup, inventory holding, and material consumed costs. We present two mathematical models: the Gilmore-Gomory model and the Arc flow model. In addition, two heuristics are proposed: a column generation-based heuristic (CGH) and a dynamic programming-based heuristic (IDPH). Extensive experimental studies are executed based on randomly generated instances. The computational results show that the Gilmore-Gomory model works better than the Arc flow model for the capacitated multi-period cutting stock problem with pattern setup cost. Moreover, the two heuristics are comparable, as both can obtain high quality solutions. Statistical analyses are also performed to verify these conclusions.

In this paper we address the classical hybrid flow shop scheduling problem with makespan objective. As this problem is known to be NP-hard and a very common layout in real-life manufacturing scenarios, many studies have been proposed in the literature to solve it. These contributions use different solution representations of the feasible schedules, each one with its own advantages and disadvantages. Some of them do not guarantee that all feasible semiactive schedules are represented in the space of solutions –thus limiting in principle their effectiveness– but, on the other hand, these simpler solution representations possess clear advantages in terms of having consistent neighbourhoods with well-defined neighbourhood moves. Therefore, there is a trade-off between the solution space reduction and the ability to conduct an efficient search in this reduced solution space. This trade-off is determined by two aspects, i.e. the extent of the solution space reduction, and the quality of the schedules left aside by this solution space reduction. In this paper, we analyse the efficiency of the different solution representations employed in the literature for the problem. More specifically, we first establish the size of the space of semiactive schedules achieved by the different solution representations and, secondly, we address the issue of the quality of the schedules that can be achieved by these representations using the optimal solutions given by several MILP models and complete enumeration. The results obtained may contribute to design more efficient algorithms for the hybrid flow shop scheduling problem.

The main objective of this paper is to solve the optimization problem that is associated with the classification of DNA samples in PCR plates for Sanger sequencing. To achieve this goal, we design an integer linear programming model. Given that the real instances involve the classification of thousands of samples and the linear model can only be solved for small instances, the paper includes a heuristic to cope with bigger problems. The heuristic algorithm is based on the simulated annealing technique. This algorithm obtains satisfactory solutions to the problem in a short amount of time. It has been tested with real data and yields improved results compared to some commercial software typically used in (clinical) laboratories. Moreover, the algorithm has already been implemented in the laboratory and is being successfully used.

Customer Order Scheduling Problem (COSP) with minimisation of the total completion time as the objective is NP-Hard. COSP has many applications that include the pharmaceutical and the paper industries. However, most existing COSP algorithms struggle to find very good solutions in large-sized problems. One key reason behind is that those algorithms are based on generic templates and as such lack problem specific structural knowledge. In this paper, we capture such knowledge in the form of heuristics and then embed those heuristics within constructive and perturbative search algorithms. In the proposed deterministic constructive search algorithm, we use processing times in various ways to obtain initial dispatching sequences that are later used in prioritising customer orders during search. We also augment the construction process with solution exploration. In the proposed stochastic perturbative search, we intensify its diversification phase by prioritising rescheduling of customer orders that are affected badly. Our tailoring of the search in this case is to make informed decisions when the search has lost its direction. On the contrary to that, in the intensification phase, we then take diversifying measures and use multiple neighbourhood operators randomly so that the search does not get stuck very quickly. Our experimental results show that the proposed algorithms outperform existing state-of-the-art COSP algorithms.

This paper addresses the distributed limited-buffer flowshop scheduling problem with makespan minimization criterion for the first time. The manufacturing layout consists of multiple homogeneous factories and each one is set as a permutation flowshop with limited buffers between any two adjacent machines. Compared with traditional single shop scheduling, this problem is more realistic because of the distribution and limited buffer constraints. Given that the NP-hardness, this paper focuses on the approximate approaches, and successively proposes two constructive heuristics for generating fast schedule and providing good initialization of meta-heuristics, a differential evolution algorithm run in continuous search space to further better the so-obtained schedules, and a discrete differential evolution algorithm implemented directly in combinatorial search space. Extensive experimental results validate that the performance of discrete differential evolution perform the best and other algorithms proposed in this paper are all with satisfactory evaluations.

This paper presents a comprehensive and novel mathematical model to address the scheduling problem of inpatient surgeries. The interaction quality and compatibility level of surgical team members can have a significant impact on the quality and safety of a surgery. The first aim of this paper is to incorporate the decision-making styles of the surgical team members (as a personality indicator) in an operating room scheduling problem to improve the compatibility level within the surgical teams. The second aim of this paper is to provide a more effective and realistic solution for the problem by considering several practical factors. These factors include the availability of material resources (i.e., operating rooms, post-anesthesia beds, and equipment), priorities of patients, and availability, skills, and competencies of the surgical personnel. To cope with the computational complexity of the problem, two metaheuristics (i.e., NSGA-II and MOPSO) are developed to find Pareto solutions. Furthermore, the PROMETHEE-II method is used to select the best among the obtained Pareto solutions. Finally, a real case study is provided to show the applicability of the developed approach.

This paper considers the Quay Crane Scheduling Problem (QCSP) with non-crossing and safety clearance constraints for a single vessel. The problem determines the order of unloading and loading operations that a specific number of quay cranes (QCs) perform to serve a vessel in minimum time. The QCs move on a single rail and therefore cannot cross each other, and every two consecutive cranes must leave a specific safety distance between them. Due to the difficulty of this problem, most researchers have used heuristics to solve it. However, the QCSP is normally used as a building block of bigger ports’ optimization problems that are very difficult to solve without some decomposition techniques like Lagrangian relaxation. For these methods to succeed, the sub-problems must be solved to optimality in reasonable computational time. This paper presents an improvement on a recent novel formulation for the problem, followed by a new exact and computationally fast technique to solve it. The technique is a two-step approach initiated by a partitioning heuristic and terminated by a Branch and Price algorithm. Through computational experiments, we demonstrate that the proposed solution approach can solve real-sized cases in a fast computational time and has low sensitivity to all parameters. Finally, we introduce a method, formulated as a traveling salesman problem, to acquire operationally practical solutions by minimizing crane re-positioning movements and accounting for crane initial positions.

The search for logistics best-practices in international trade has led to the appearance of the Berth Allocation Problem. If the vessels have release dates, the problem is proved to be NP-hard and the performance of exact algorithms is not satisfactory, leading to the use of metaheuristics. This paper develops a Hybrid Evolutionary Algorithm for the discrete and dynamic Berth Allocation Problem. A challenge of using Genetic Algorithms is the identification of the best approach to model a specific problem. This paper proposes the use of frontier techniques (Data Envelopment Analysis and Free Disposal Hull models) to compare the performances of alternative specifications of the parameters for the algorithm proposed and to identify efficient solutions.

Additive manufacturing (AM), also known as 3D printing, is gaining enormous importance in the production of highly customised quality and lightweight products in low quantities. In addition to AM's use in producing fully functional industrial components, it is also seen as a technology of the future that will enable civilisation in space. Although the cost structures for AM facilities have been sufficiently studied in the literature, no effort has been made to investigate the scheduling problem of AM machines with the aim of optimising processing time-related performance measures. This paper focuses on the scheduling problem of single and multiple AM machines and proposes mathematical models for optimisation. Mixed-integer linear programming models allocate parts into jobs to be produced on AM machines to minimise makespan. The problem was handled by considering different machine configurations (i.e. single machine, parallel identical machines, and parallel non-identical machines). The models were coded in IBM ILOG CPLEX Optimization Studio (v12.8.0) and solved through the CPLEX solver. This paper presents detailed solutions for numerical examples. A comprehensive computational study was also conducted, and the results are presented. The optimum solutions are reported for most problems. The best solutions obtained within the time limit (i.e. 1800 and 2400 s) are reported for the parallel identical and non-identical AM machine scheduling problems if optimum solution could not be verified.

In this paper, we extend traditional hub location models for an intermodal network design on a sparse network structure. While traditional hub location problems have been employed for developing network designs for many specific applications, their general assumptions – such as full connectivity, uniform transfer mode, and direct connections between access nodes and hubs – restrict their direct applicability to real-world logistics problems in several ways. In many network design contexts, the usage of versatile transfer modes and hubs is required due to different pricing of modes and topological considerations. In this paper, we extend the traditional hub location problem by incorporating three transfer modes and two kinds of hubs. As an important additional modification, we do not assume that the underlying network is fully connected, or that hubs and access nodes are directly connected. The context for our modelling is intermodal container movements in an archipelago. We develop and formulate an intermodal hub location problem. We show that this problem is NP-hard. Furthermore, a dataset for intermodal hub location problem is provided, based on a real-world container distribution problem in Indonesia. This dataset involves three modes of transport and a sparse network structure. We perform computational experiments and analyse our computational results. Our model provides insights for decision making and determining pricing policies for the desired levels of network flow.

© 2018 Elsevier Ltd The goal of this paper is to investigate the impact of different solution representations, as part of a metaheuristic approach, on net present value optimization in project scheduling. We specifically consider the discrete time/cost trade-off problem with net present value optimization and apply three payment models from literature. Each of these models determines the timing and size of cash flows from the contractor's viewpoint. The contribution of this paper to literature is twofold. First, we include cash flow distribution variants in the payment models, to also distinguish between different manners in which value is created and costs are incurred, as part of a general model for the contractor's cash flow management. This general model is developed in order to explicitly include the progress of activities in the determination of the timing and size of payments to the contractor, which is currently lacking in literature. Second, we employ an iterated local search framework to compare different solution representations and their corresponding local search and repair heuristics. The goal is to unambiguously show that the choice of a solution representation deserves a fair amount of attention, alongside the selection of appropriate diversification and intensification operators, even though this is not always the case in literature. Each part of the proposed algorithm is validated on a large dataset of test instances, generated to allow for a broad comparison of the solution representations. Our results clearly quantify the statistically significant differences between three types of representations for the project scheduling problem under study. ispartof: Computers and Operations Research vol:103 pages:184-197 status: published

[EN] Parallel machine scheduling problems have many practical and industrial applications. In this paper we study a generalization which is the unrelated parallel machine scheduling problem with machine and job sequence setup times (UPMS) with makespan minimization criterion. We propose new mixed integer linear programs and a mathematical programming based algorithm. These new models and algorithms are tested and compared with the existing ones in an extensive and comprehensive computational campaign. The performance of two popular commercial solvers (CPLEX and Gurobi) is also compared in the experiments. Results show that the proposed methods significantly improve on existing methods and are able to obtain solutions for extremely large instances of up to 1000 jobs and eight machines with relative deviations from lower bounds below 0.8%., The authors are partially supported by the Spanish Ministry of Economy and Competitiveness, under the project SCHEYARD Optimization of Scheduling Problems in Container Yards (No.DPI2015-65895-R) financed by FEDER funds. Special thanks are due to our colleague Alfredo Marín, for fruitful discussions that helped improve this paper and to Tran and coauthors for all the help received during the reimplementation of their efficient methods. Thanks are also due to three anonymous referees for their helpful reports.

This paper addresses the time-optimal trajectory planning for autonomous underwater vehicles. A detailed mixed integer nonlinear programming (MINLP) model is presented, explicitly taking into account vehicle kinematic constraints, obstacle avoidance, and a nonlinear flow field to represent the ocean current. MINLP problems pose great challenges because of the combinatorial complexity and nonconvexities introduced by the nature of the flow field. A novel solution approach in an optimization framework is developed to address associated difficulties. The main benefit of the proposed methodology is the ability to find multiple local minima. The contribution of the paper is fourfold: (1) a novel approach to integrate the flow field into the MINLP model; (2) a diversified initialization strategy using multiple waypoints, different solvers and approximated models, namely, a mixed integer linear programming model and the MINLP model with and without the flow field; (3) an algorithm that forces the solver to seek improved solutions; and (4) a parallel computing approach capitalizing on diversified initialization. The performance of the resulting methodology is illustrated on idealized case studies, and the results are used to gain insight into trajectory planning in the presence of flow fields.

This paper addresses a special vehicle routing problem, which extends the classical problem by considering the time window and synchronized-services constraints. A time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. This problem has many practical applications such as caregiver scheduling problem encountered in the home health care industry. The synchronization constraints in this problem interconnect various vehicles’ routes, making the problem more challenging than standard vehicle routing problem with time windows, especially in designing neighborhood search-based methods. A mixed-integer programming model is proposed for the problem. Motivated by the challenge of computational time, an efficient Adaptive Large Neighborhood Search heuristic is proposed to solve the problem. The approach is evaluated on benchmark instances acquired from the literature and new large-scale test instances first generated in this paper. The numerical results indicate that our solution method is able to outperform existing approaches.

Lot sizing is one of the most challenging problems in production planning. This paper focuses on the multi-plant capacitated lot sizing problem (MPCLSP) with setup carry-over (MPCLSP-SC). To the best of our knowledge, the MPCLSP-SC has been the subject of one single study, despite the fact that it can bring financial benefits, primarily by considering case studies under tight capacity. Moreover, in spite of the significant improvement in the performance of benchmark optimization solvers over the years, they are still very time and memory consuming for large MPCLSP instances. Therefore, heuristics stand out among the solution methods to tackle this type of problem. This paper introduces a novel matheuristic, a kernel search (KS) method, to solve the MPCLSP-SC. Through computational experiments, it was possible to show the outstanding performance of the proposed method for large instances with diverse characteristics. The experiments also demonstrate that the introduced KS outperformed state-of-the-art methods to solve the MPCLSP.

Shift Minimization Personnel Task Scheduling Problem (SMPTSP) is assigning a given set of predetermined tasks (with known start and finish times) to a minimum number of heterogeneous workers with predetermined shifts. Each task can be performed only by a specific subset of workers. Every task must be assigned to a worker. A worker cannot perform more than one task at a time, and tasks cannot be pre-empted. SMPTSP is NP-hard, but there is practical interest in solving very large instances of it in ground crew scheduling of a large airline in a large airport. Recently, there have been a few papers reporting various solution methods for large instances of SMPTSP. However, solving very large instances of SMPTSP remains a challenge. In this paper, we propose a novel greedy heuristic solution method for SMPTSP. A reduced problem is solved iteratively by selecting the best possible assignment of tasks to one worker. We have tested the Greedy heuristic method on 3 sets of available large test problems. The results show that the heuristic method performs well relative to the current solution methods, and has the added advantage of being able to solve very large instances fast.

Exacerbated urban road congestion is a real concern for transportation authorities around the world. Although agent-based simulation and iterative design approaches are typically used to provide solutions that reduce congestion, they fall short of meeting planners’ need for an intelligent network design system. Since Markov chains are remarkably capable of modeling complex, dynamic, and large-scale networks, this paper leverages their theory and proposes a mathematical model based on Markov chain traffic assignment (MCTA) to optimize traffic and alleviate congestion through targeted direction conversions, i.e. two-way to one-way flow conversions. The approach offers an intelligent traffic pattern design system, one which can analyze an existing complex network and suggest solutions taking into consideration network-wide interdependencies. Specifically, the paper presents a binary nonlinear mathematical model to optimize road network traffic patterns using maximum vehicle density. The model is then solved using Genetic Algorithm (GA) optimization methodology, and a fine-tuning search algorithm is proposed to improve upon GA results in terms of solution's practicality and fitness. The approach is applied to a city setting and experimental results are reported. Finally, an application in time-sensitive decision-making is discussed.

In this paper, we study the Cardinality Constrained Multi-cycle Problem (CCMcP) and the Cardinality Constrained Cycle and Chain Problem (CCCCP). A feasible solution allows one or more cardinality-constrained cycles to exist on the digraph. A vertex can only be involved in at most one cycle, and there may be vertices not involved in any cycles. The CCCCP has an additional set of vertices that can only serve–and are the only vertices that can serve–as the starting vertex of a chain. Apart from cycles, a feasible solution to the CCCCP may also contain multiple cardinality-constrained chains. A vertex can be involved in a chain or a cycle, but not both. Both of the CCMcP and the CCCCP are NP-hard. This paper focuses on the polyhedral study of the arc-based formulations for both problems. We prove that 3 classes of constraints are facet-defining for the CCMcP polytope, identify 4 new classes of constraints and prove their validity. We then prove that the non-negativity and the degree constraints are facet-defining for the CCCCP polytope. Even though we cannot expect to find a complete polyhedral description (CPD) of the CCMcP or the CCCCP, as both problems are NP-hard, any partial description is always interesting for both theoretical and computational purposes, since the wider the linear description, the less need for branching. A CPD is composed of facet-defining constraints, hence the major contribution of this paper is one step towards finding a CPD for the CCMcP and the CCCCP. We tested the strengths of the facet-defining constraints and new valid constraints on two sets of randomly generated data instances. We reported the numerical results and discussed future research directions.

In this paper we address the problem of electing a committee among a set of m candidates on the basis of the preferences of a set of n voters. We consider the approval voting method in which each voter can approve as many candidates as he likes by expressing a preference profile (boolean m-vector). In order to elect a committee, a voting rule must be established to ‘transform’ the n voters’ profiles into a winning committee. The problem is widely studied in voting theory; for a variety of voting rules the problem was shown to be computationally difficult and approximation algorithms and heuristic techniques were proposed in the literature. In this paper we follow an Ordered Weighted Averaging approach and study the k-sum approval voting (optimization) problem in the general case 1 ≤ k

A way to solve bi-objective problems is to use an effective single objective algorithm embedded inside an e -constraint approach. In this paper, we are interested in any Bi-Objective Vehicle Routing Problem such that if one objective is constrained, the resulting single objective optimization problem can be solved by a state-of-the-art column generation-based method. We propose mechanisms and techniques to significantly speed up the resulting algorithm. Computational experiments are conducted on two problems: the Bi-Objective Vehicle Routing Problem With Time Windows and the Bi-Objective Team Orienteering Problem with Time Windows. To the best of our knowledge, this paper presents the first exact method proposed for the first problem and the second exact method proposed for the second problem. On the first problem we demonstrate the effectiveness of the proposed mechanisms. On the second problem, our algorithm is competitive with algorithms from the literature.

The parallel stack loading problem (PSLP) is an NP-hard problem. In this problem, the objective is to optimize assigning a group of arriving items to empty slots of parallel stacks in a storage bay. The PSLP aims to find a bay configuration that minimizes the future retrieval effort of these items. The retrieval effort is generally represented by the number of relocations needed during retrieval. These relocations are obligatory when an item not located at the top of a stack is to be retrieved. The number of relocations for a given bay configuration is minimized by another NP-hard problem, called the block relocation problem (BRP). The simultaneous solution of the PSLP and the BRP is complicated. As an alternative, previous literature studies proposed using a surrogate objective function (SOF) to approximate the number of relocations in the PSLP. This paper proposes two new SOFs which result in bay configurations with a minimized retrieval effort. Also, this paper introduces a new method to represent the retrieval effort. The new method considers the number of empty slots needed for relocations as well as the number of relocations. Extensive computational studies are provided to verify the proposed SOFs, and illustrate that they outperform other SOFs from the literature.

Over the years, methods and algorithms have been extensively studied to solve variations of the rectangular two-dimensional strip packing problem (2D-SPP), in which small rectangles must be packed inside a larger object denominated as a strip, while minimizing the space necessary to pack all rectangles. In the rectangular 2D-SPP, constraints are used to restrict the packing process, satisfying physical and real-life practical conditions that can impact the material cutting. The objective of this paper is to present an extensive literature review covering scientific publications about the rectangular 2D-SPP constraints in order to provide a useful foundation to support new research works. A systematic literature review was conducted, and 223 articles were selected and analyzed. Real-life practical constraints concerning the rectangular 2D-SPP were classified into seven different groups. In addition, a bibliometric analysis of the rectangular 2D-SPP academic literature was developed. The most relevant authors, articles, and journals were discussed, and an analysis made concerning the basic constraints (orientation and guillotine cutting) and the main solving methods for the rectangular 2D-SPP. Overall, the present paper indicates opportunities to address real-life practical constraints.

An attractive way to reduce losses in electric power distribution networks is addressing the network reconfiguration problem, which should give a topology for the primary distribution network that minimizes the total losses due to the electrical resistances in the lines and complementary equipment’s ( technical losses ). Distributed energy resources and additional innovations associated to smart grids allow enhancing the benefits of finding better network topologies. On the other hand, the integration of renewable energy sources with variable random outputs requires expanding the perspective in modeling the network reconfiguration problem and in the shaping of appropriate solution techniques. These issues are the object of this paper. The main new features of the problem are explored with a maquette designed to highlight the consequences of random generation sources in the networks. Following, the paper proposes a formulation for the problem that explicitly considers random energy sources. A state of the art genetic algorithm build under the biased random-key evolution framework (BRKGA) is developed to address this hard combinatorial optimization problem. Case studies with benchmark networks put into perspective the proposed methodology. Results show that random energy values should be explicitly modeled in contemporary approaches to the network reconfiguration problem. The paper provides the grounds for addressing this new problem and points to additional research paths in the area.

This paper addresses the wind farm contribution in frequency control during the integration in the power grid. In the proposed model, the wind farm utilizes inertia control and droop control techniques with the purpose of improving the frequency regulation. In order to achieve optimal results, all the parameters of the controllers for the different units in the power grid are obtained by using a particle swarm optimization algorithm (PSO) and by introducing a modified objective function instead of a conventional objective function e.g., Integral Time-weighted Absolute Error (ITAE). Also, different constraints such as reheat turbine, time delay, governor dead band and generation rate constraint (GRC) are considered for thermal and hydro units with the aim of studying a more realistic power system, which is the main contribution of this paper when compared to the oth0er works in this field. It is shown that, in case of a perturbation in power demand, the system frequency will recover quickly and effectively in comparison with the traditional approaches. In addition, a sensitivity test is carried out in a single power grid area in order to examine the effectiveness of the proposed approach. Then, the system is extended to a multi-area power system using a multi-terminal HVDC for further investigation of the suggested strategy. Simulation results are presented in order to assess the performance of the proposed approach in the power system.

In a partial shop scheduling problem the operations of each job have to respect a partial order, which can be different for each job. We study the problem of finding a solution of minimal makespan in partial shops. This problem generalizes many problems which have been studied independently in the literature, such as the group shop scheduling problem, the mixed shop scheduling problem, and the open shop scheduling problem. In this paper we propose an algorithm which is able to find solutions for the partial shop scheduling problem. In computational experiments we find that the proposed single heuristic can compete with the state-of-the-art heuristics for the partial shop, group shop, mixed shop, and open shop, and in many cases, improves the state of the art. The main contribution of this paper is the demonstration that a single algorithm can solve effectively many special cases of the partial shop without taking into consideration their particular structure. We highlight the contribution of the main novel components of the algorithm, namely the initial solution generator, neighbourhood structure, and the lower bound for new solutions generated by such neighbourhood.

In the Vehicle Routing Problem with Backhauls (VRPB), the customer set is partitioned into linehaul customers who require deliveries, and backhaul customers who require pickups. Both the linehaul customers and the backhaul customers must be visited contiguously, and all routes must contain at least one linehaul customer. All deliveries have to be loaded at the depot, and all pickups up have to be transported to the depot. This survey paper aims to comprehensively review the existing literature on VRPBs, including models, exact and heuristic algorithms, variants, industrial applications and case studies, with an emphasis on the recent literature. The paper contains several synthetic tables and proposes a number of promising research directions.

Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically, we apply a mathematical programming formulation and several heuristic methods based on the tabu search methodology to solve it. In line with the previous paper on this topic, we consider bipartite graphs in our experimentation. The extensive computational experiments with more than 1000 instances show the superiority of our proposals in both, quality and computing time.

In this paper, we consider a special case of vehicle routing problem that addresses the routing problem in a semiconductor supply chain. This paper proposes two Mixed Integer Linear Programming (MILP) models for solving the Green Vehicle Routing Problems with Pickups and Deliveries in a Semiconductor Supply Chain (G-VRPPD-SSC). The first MILP model considers the basic G-VRPPD-SSC problem, and the objective is to find the set of minimum cost routes and schedules for the alternative fuel vehicles in order to satisfy a set of requests which comprise pickup and delivery operations, without violating the product and vehicle compatibility, vehicle capacity, request-priorities and request-types, and start/completion time constraints. The second model extends the first model in order to handle the scenario of having different fuel prices at different refueling stations, and the objective is to minimize the sum of costs of operating alternative fuel vehicles, which include both the routing cost and the refueling cost. To relatively evaluate the performance of the proposed MILP models, we consider the Pickup and Delivery Problem in a Semiconductor Supply Chain (PDP-SSC) without the presence of alternative fuel vehicles, and we present the corresponding MILP model. Our model is compared with an MILP model present in the literature. Our study indicates that the proposed model for the PDP-SSC gives better lower bounds than that by the existing work, apart from performing better than the existing work in terms of requiring less CPU time. In all cases, the proposed three MILP models preform quite good in terms of the execution time to solve the generated problem instances.

This paper addresses the customer order scheduling problem in parallel production environment commonly appearing in the pharmaceutical and paper industries. The problem aims to minimize the total completion time of the orders with their jobs processed on dedicated machines in parallel. To deal with the computational challenge of large-scale problems, we propose a learning-based two-stage optimization method consisting of a learned dispatching rule in the first stage and an adaptive local search in the second stage. The new dispatching rules are automatically generated by the proposed feature-enhanced genetic programming method in an off-line learning manner. Based on the high-quality initial solutions provided by the learned dispatching rule, we develop an adaptive local search to further improve the solution quality. Numerical results indicate the superiority of the learned dispatching rule and show the proposed two-stage optimization method significantly outperforms state-of-the-art methods in the literature.

Intermodal transportation plays a key role in modern transportation systems. There is a high interest into design efficient and low-cost intermodal networks. In this paper, we review more than 100 papers on recent literature regarding intermodal network design from a hub location perspective. We discuss recent trends and provide more than 20 future research directions focused on the modeling of realistic intermodal transportation systems. Findings and research directions are structured in terms of the modeling of internal and external factors and solution features, and we found that current models lack of realism in the modeling of internal factors of intermodal hub networks like hubs and vehicles.

Time-dependent prize-collecting arc routing problems (TD-PARPs) generalise the regular prize-collecting arc routing problems (PARPs). PARPs have arcs associated with collectable prizes along with travelling costs. TD-PARPs allow travel times to vary at the travelling horizon so that real-life uncertain factors such as traffic and weather conditions can be taken into account. A TD-PARP is to find a travelling route that maximises the profit i.e. total collected prizes minus total travelling costs. TD-PARPs have two facets: selecting a subset of arcs to be travelled and scheduling the selected arcs in the travelling route. TD-PARPs have not been studied much although they are more realistic and generic. In this paper, we first propose a set of deterministic heuristic search algorithms that range from a simple procedure producing quite good results in a fraction of a CPU second to a more extensive procedure producing high-quality results but at the expense of slightly extra CPU time. In this paper, we then propose a meta-heuristic based scatter search (SS) algorithm for TD-PARPs. For the improvement method in the SS algorithm, we propose a multi-operator algorithm that incorporates various neighbourhood operators to diversify the local exploration. For the combination method in the SS algorithm, we propose a 2-level path relinking procedure, which explores combinations of visited and unvisited arcs using two different operators. To control the diversity of the solutions in the SS algorithm, we propose a new effective distance measurement. The experimental results on standard benchmark problems indicate that the proposed SS algorithm significantly outperforms the state-of-the-art existing methods.

Extended technical precedence constraints (ETPC) in dynamic job shop scheduling problem (DJSP) are the precedence constraints existing between different jobs instead of the conventional technical precedence constraints existing in the operations of the same job. This paper presents the mathematical programming model of the DJSP with ETPC to minimize the mean weighted tardiness of the jobs. The mathematical model contributes to the solution and modelling of the DJSP with ETPC and it is used to solve small-sized problems to optimality. To solve industry-sized problems, a constructive heuristic called the dispatching rule (DR) is employed. This paper investigates the use of genetic programming (GP) as a hyper-heuristic in the automated generation of the problem-specific DRs for solving the problem under consideration. The genetic programming-based hyper heuristic (GPHH) approach constructs the DRs which are learned from the training instances and then verified on the test instances by the simulation experiments. To enhance the efficiency of the approach when evolving effective DRs to solve the problem, the approach is improved with strategies which consist of a problem-specific attribute selection for GP and a threshold condition mechanism for fitness evaluation. The simulation results verify the effectiveness and efficiency of the evolved DRs to the problem under consideration by comparing against the existing classical DRs. The statistical analysis of the simulation results shows that the evolved DRs outperform the selected benchmark DRs on the problem under study. The sensitivity analysis also shows that the DRs generated by the GPHH approach are robust under different scheduling performance measures. Moreover, the effects of the model parameters, including the percentage of jobs with ETPC and the machine utilization, on the performance of the DRs are investigated.

The Min–Max Arc Crossing Problem (MMACP) aims to minimize the maximum number of crossings over all arcs in a layered graph. It is a recently proposed variant of the well-known graph drawing problem where the total number of arc crossings is minimized. MMACP is of interest in VLSI design and graph visualization, especially when dealing with very large graphs. In this paper, we present a variable depth neighborhood search algorithm for solving MMACP. Our algorithm exploits good data structures, efficient neighborhood search schemes, and a carefully defined ejection chain scheme. Effectively embedding these basic structures within an iterated local search framework, our algorithm produced superior outcomes. In particular, the algorithm produced new solutions improving the best-known results for 154 out of the 301 benchmark instances available in the public domain. As a result, our paper enhances the state-of-the-art knowledge in graph drawing and arc crossing minimization. We also computationally analyzed the roles and effectiveness of various crucial features of our algorithm which helped us make informed recommendations for default parameter settings.

The problem of scheduling jobs to minimise completion time variance (CTV) is a well-known problem in scheduling research. CTV is categorized as a non-regular performance measure and its value may decrease by increasing the job completion times. This objective is relevant in situations where providing uniform service to customers is important, and is in-line with just-in-time philosophy. The problem concerned in this paper is to schedule n jobs on two identical parallel machines to minimise CTV. We consider the unrestricted version of the problem. The problem is said to be restricted when a machine is not allowed to remain idle when jobs are available for processing. It may be necessary to delay the start of job processing on a machine in order to reduce the completion time deviations. This gives rise to the unrestricted version of the problem. We discuss several properties of an optimal schedule to the problem. In this paper, we develop a lower bound on CTV for a known partial schedule and propose a branch and bound algorithm to solve the problem. Optimal solutions are obtained and results are reported.

In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a modular way, as a factor of the number of flights. We propose heuristic methods to obtain high-quality solutions in short computing times. Specifically, we implement memory structures to create advanced search methods and compare them with previous heuristics on a set of benchmark instances. Memory structures have been widely implemented in the context of the tabu search methodology, usually embedded in local search algorithms. In this paper we explore an alternative design in which the constructive method is enhanced with frequency information and the local search is coupled with a path relinking post-processing. Statistical tests confirm the superiority of our proposal with respect to previous developments.

The Time Capacitated Arc Routing Problem (TCARP) extends the classical Capacitated Arc Routing Problem by considering time-based capacities instead of traditional loading capacities. In the TCARP, the costs associated with traversing and servicing arcs, as well as the vehicle’s capacity, are measured in time units. The increasing use of electric vehicles and unmanned aerial vehicles, which use batteries of limited duration, illustrates the importance of time-capacitated routing problems. In this paper, we consider the TCARP with stochastic demands, i.e.: the actual demands on each edge are random variables which specific values are only revealed once the vehicle traverses the arc. This variability affects the service times, which also become random variables. The main goal then is to find a routing plan that minimizes the expected total time required to service all customers. Since a maximum time capacity applies on each route, a penalty time-based cost arises whenever a route cannot be completed within that limit. In this paper, a strategic oscillation simheuristic algorithm is proposed to solve this stochastic problem. The performance of our algorithm is tested in a series of numerical experiments that extend the classical deterministic instances into stochastic ones.

Most existing facility location and network design models assume the facility cost as either a fixed cost term or a linear/concave function of the volume of demand assigned to a facility. In particular, a concave cost function implies decreasing marginal cost and exhibits economies of scale. However, when the assigned demand volume exceeds a certain level, diseconomies of scale may occur due to facility congestions, overuse of resources, increasing operational complexity, and so on, leading to a convex cost function with increasing marginal cost. This paper studies a warehouse–retailer network design problem, which simultaneously optimizes the warehouse locations, the warehouse–retailer assignment, and the multi-echelon inventory replenishment policy to minimize the total cost, including the warehouse location and operating costs, the inventory replenishment cost, and the transportation cost. In this paper, the warehouse operating cost is defined as a general function of the volume of demand assigned to a warehouse, which could be concave first due to economies of scale and then convex due to diseconomies of scale. We formulate this problem as a set-covering model and propose a column generation algorithm to solve its linear relaxation. The pricing problem of the column generation process, although formulated as a nonlinear mixed integer program, has nice structural properties and can be solved efficiently by a branch-and-bound method. To validate the effectiveness and efficiency of the proposed column generation algorithm, we conduct numerical studies based on randomly generated instances. Numerical results also demonstrate the impact of economies and diseconomies of scale on network design decisions and warehouse operating cost.

Batch scheduling involves a machine that can process several jobs simultaneously. The existing literature mainly focuses on the batch-size-dependent setup time. However, setup time depends not only on the batch size but also on technological characteristics. This paper investigates a single batch scheduling problem with dual quantitative and technological setup times extracted from autoclave molding production. A mixed-integer linear programming model (MILP) is established, in which the objective function is to minimize the makespan. The quantitative setup time is linear with the batch size, whereas the technological setup time is nonlinear with the occupied area of all jobs (jobs are represented by rectangles) in a batch. Three lower bounds are presented for evaluating the proposed algorithms. Then, a two-stage approximate algorithm is designed to solve the problem. The first stage concerns the normal batch processing time. In the second stage, an iterative local search method focuses on all terms in the objective function and improves the current solution’s quality. Finally, different scales of instances are designed to test the effectiveness and efficiency of the algorithms. Statistical analysis shows that the proposed algorithm in this paper can handle the problem well compared to other algorithms.

Appointment scheduling has many applications (e.g., surgery scheduling, airport gate scheduling, container vessel dockings and radiation therapy bookings) and it has a direct and significant operational and economic impact. For example, in healthcare, surgical departments are one of the main drivers of hospital costs and revenue, and appointment scheduling is used to book surgeries. Effective scheduling not only enables patients’ timely access to care but also enables more efficient operations. This becomes especially important as healthcare costs and demand are on the rise in many countries. We study appointment scheduling where there are jobs (e.g., patients, container vessels, airplanes) with random processing durations, an expensive processor (e.g., a doctor, dock crane, airport gate) and significant costs for processor idle time, processor overtime, and job waiting. The goal is to determine an appointment schedule that minimizes a measure of total costs as the objective. The appointment scheduling problem has been well studied in the literature with the expected cost objective. Almost all papers in the literature on appointment scheduling use the expected cost criterion, which may not be suitable when risk measures and/or service levels are considered. In this paper, we study this problem with a new objective: minimization of any quantile of the cost distribution, e.g., median, 90th percentile. We obtain theoretical results for some special cases and develop an algorithm for the general case. Our algorithm does not require a specific distribution assumption and can work directly with data samples. We present numerical examples with real data on surgeries. Our results show that allocated schedules based on the quantile objective with identical jobs are different than the ones generated by the expected cost objective and they do not show the well-known dome-shaped pattern but a semi-dome-shaped pattern which first increases (like the dome-shaped pattern) but then its decrease is not monotone (unlike the dome-shaped pattern). To the best of our knowledge, this is the first paper on appointment scheduling problem with the objective of the quantile function minimization.

Additive manufacturing – also known as 3D printing – is a manufacturing process that is attracting more and more interest due to high production rates and reduced costs. This paper focuses on the scheduling problem of multiple additive manufacturing machines, recently proposed in the scientific literature. Given its intractability, instances of relevant size of additive manufacturing (AM) machine scheduling problem cannot be solved in reasonable computational times through mathematical models. For this reason, this paper proposes a Reinforcement Learning Iterated Local Search meta-heuristic, based on the implementation of a Q-Learning Variable Neighborhood Search, to provide heuristically good solutions at the cost of low computational expenses. A comprehensive computational study is conducted, comparing the proposed methodology with the results achieved by the CPLEX solver and to the performance of an Evolutionary Algorithm recently proposed for a similar problem, and adapted for the AM machine scheduling problem. Additionally, to explore the trade-off between efficiency and effectiveness more deeply, we present a further set of experiments that test the potential inclusion of a probabilistic stopping rule. The numerical results evidence that the proposed Reinforcement Learning Iterated Local Search is able to obtain statistically significant improvements compared to the other solution approaches featured in the computational experiments.

The multiple traveling salesmen problems ( mTSP ) are variants of the well-known traveling salesmen problems, in which n cities are to be assigned to m salespeople. In this paper, we propose an evolution strategy ( ES ) approach for solving the mTSP with minsum and minmax objectives. The ES employs a self-adaptive Ruin and Recreate ( RR ) heuristic to generate an offspring population. In the RR heuristic, some solution components are removed from a solution and the removed components are reinserted into the partial solution to obtain a new complete solution again. We employ the Multiple Insertion Heuristic ( MIH ) when carrying out insertions with the speed-up method based on the nearest neighbor approach in the recreate procedure. Through the ES , the ruin size parameter of the RR heuristic and the selection probabilities of applying a random search algorithm consisting of four different moves are self-adapted. 3 O p t local search is also embedded in the ES to further enhance the solution quality. A Boolean flag is developed whether or not to apply 3 O p t local search, which is computationally expensive, on non-improving tours. Moreover, new constructive heuristics are presented for both minsum and m inmax mTSP . Computational experiments show that the proposed ES algorithm is very competitive or superior to the best performing algorithms from the literature for both objectives. Ultimately, 21 new best-solutions are presented for the mTSP with minsum and minmax objectives for the first time in the literature. In this paper, the multi-depot mTSP with non-predetermined depots ( M - mTSP ) is also studied as an extension of the mTSP . Two new MILP models are proposed for both minsum and minmax M - mTSP as well as lower bounds, and optimal results are obtained for small instances. The computational results show that the ES algorithm can find the optimal solution for all the small-sized instances. Furthermore, we derive new large-sized M - mTSP benchmarks from the well-known TSPLIB, which have nodes ranging from 52 and 442. We report the results for both minsum and minmax objectives for these instances as new M - mTSP benchmarks, considering four different m settings.