A nettó jelenérték maximalizálása erőforrás-korlátos projektekben - egy új harmóniakereső metaheurisztika (A harmony search metaheuristic for the resourceconstrained project scheduling problem with discounted cash flows)

Ebben a tanulmányban a szerző egy új harmóniakereső metaheurisztikát mutat be, amely a minimális időtartamú erőforrás-korlátos ütemezések halmazán a projekt nettó jelenértékét maximalizálja. Az optimális ütemezés elméletileg két egész értékű (nulla-egy típusú) programozási feladat megoldását jelenti, ahol az első lépésben meghatározzuk a minimális időtartamú erőforrás-korlátos ütemezések időtartamát, majd a második lépésben az optimális időtartamot feltételként kezelve megoldjuk a nettó jelenérték maximalizálási problémát minimális időtartamú erőforrás-korlátos ütemezések halmazán. A probléma NP-hard jellege miatt az egzakt megoldás elfogadható idő alatt csak kisméretű projektek esetében képzelhető el. A bemutatandó metaheurisztika a Csébfalvi (2007) által a minimális időtartamú erőforrás-korlátos ütemezések időtartamának meghatározására és a tevékenységek ennek megfelelő ütemezésére kifejlesztett harmóniakereső metaheurisztika továbbfejlesztése, amely az erőforrás-felhasználási konfliktusokat elsőbbségi kapcsolatok beépítésével oldja fel. Az ajánlott metaheurisztika hatékonyságának és életképességének szemléltetésére számítási eredményeket adunk a jól ismert és népszerű PSPLIB tesztkönyvtár J30 részhalmazán futtatva. Az egzakt megoldás generálásához egy korszerű MILP-szoftvert (CPLEX) alkalmaztunk. _______________ This paper presents a harmony search metaheuristic for the resource-constrained project scheduling problem with discounted cash flows. In the proposed approach, a resource-constrained project is characterized by its „best” schedule, where best means a makespan minimal resource constrained schedule for which the net present value (NPV) measure is maximal. Theoretically the optimal schedule searching process is formulated as a twophase mixed integer linear programming (MILP) problem, which can be solved for small-scale projects in reasonable time. The applied metaheuristic is based on the "conflict repairing" version of the "Sounds of Silence" harmony search metaheuristic developed by Csébfalvi (2007) for the resource-constrained project scheduling problem (RCPSP). In order to illustrate the essence and viability of the proposed harmony search metaheuristic, we present computational results for a J30 subset from the well-known and popular PSPLIB. To generate the exact solutions a state-of-the-art MILP solver (CPLEX) was used.

Algorithms for scheduling parallel batch processing machines with non-identical job ready times

This research is motivated by a practical application observed at a printed circuit board (PCB) manufacturing facility. After assembly, the PCBs (or jobs) are tested in environmental stress screening (ESS) chambers (or batch processing machines) to detect early failures. Several PCBs can be simultaneously tested as long as the total size of all the PCBs in the batch does not violate the chamber capacity. PCBs from different production lines arrive dynamically to a queue in front of a set of identical ESS chambers, where they are grouped into batches for testing. Each line delivers PCBs that vary in size and require different testing (or processing) times. Once a batch is formed, its processing time is the longest processing time among the PCBs in the batch, and its ready time is given by the PCB arriving last to the batch. ESS chambers are expensive and a bottleneck. Consequently, its makespan has to be minimized. ^ A mixed-integer formulation is proposed for the problem under study and compared to a formulation recently published. The proposed formulation is better in terms of the number of decision variables, linear constraints and run time. A procedure to compute the lower bound is proposed. For sparse problems (i.e. when job ready times are dispersed widely), the lower bounds are close to optimum. ^ The problem under study is NP-hard. Consequently, five heuristics, two metaheuristics (i.e. simulated annealing (SA) and greedy randomized adaptive search procedure (GRASP)), and a decomposition approach (i.e. column generation) are proposed—especially to solve problem instances which require prohibitively long run times when a commercial solver is used. Extensive experimental study was conducted to evaluate the different solution approaches based on the solution quality and run time. ^ The decomposition approach improved the lower bounds (or linear relaxation solution) of the mixed-integer formulation. At least one of the proposed heuristic outperforms the Modified Delay heuristic from the literature. For sparse problems, almost all the heuristics report a solution close to optimum. GRASP outperforms SA at a higher computational cost. The proposed approaches are viable to implement as the run time is very short. ^

The order selection and lot sizing problem in the make-to-order environment

This research is motivated by the need for considering lot sizing while accepting customer orders in a make-to-order (MTO) environment, in which each customer order must be delivered by its due date. Job shop is the typical operation model used in an MTO operation, where the production planner must make three concurrent decisions; they are order selection, lot size, and job schedule. These decisions are usually treated separately in the literature and are mostly led to heuristic solutions. The first phase of the study is focused on a formal definition of the problem. Mathematical programming techniques are applied to modeling this problem in terms of its objective, decision variables, and constraints. A commercial solver, CPLEX is applied to solve the resulting mixed-integer linear programming model with small instances to validate the mathematical formulation. The computational result shows it is not practical for solving problems of industrial size, using a commercial solver. The second phase of this study is focused on development of an effective solution approach to this problem of large scale. The proposed solution approach is an iterative process involving three sequential decision steps of order selection, lot sizing, and lot scheduling. A range of simple sequencing rules are identified for each of the three subproblems. Using computer simulation as the tool, an experiment is designed to evaluate their performance against a set of system parameters. For order selection, the proposed weighted most profit rule performs the best. The shifting bottleneck and the earliest operation finish time both are the best scheduling rules. For lot sizing, the proposed minimum cost increase heuristic, based on the Dixon-Silver method performs the best, when the demand-to-capacity ratio at the bottleneck machine is high. The proposed minimum cost heuristic, based on the Wagner-Whitin algorithm is the best lot-sizing heuristic for shops of a low demand-to-capacity ratio. The proposed heuristic is applied to an industrial case to further evaluate its performance. The result shows it can improve an average of total profit by 16.62%. This research contributes to the production planning research community with a complete mathematical definition of the problem and an effective solution approach to solving the problem of industry scale.

Formulações e algoritmos para o problema das p-medianas heterogêneo livre de penalidade

This work presents a new model for the Heterogeneous p-median Problem (HPM), proposed to recover the hidden category structures present in the data provided by a sorting task procedure, a popular approach to understand heterogeneous individual’s perception of products and brands. This new model is named as the Penalty-free Heterogeneous p-median Problem (PFHPM), a single-objective version of the original problem, the HPM. The main parameter in the HPM is also eliminated, the penalty factor. It is responsible for the weighting of the objective function terms. The adjusting of this parameter controls the way that the model recovers the hidden category structures present in data, and depends on a broad knowledge of the problem. Additionally, two complementary formulations for the PFHPM are shown, both mixed integer linear programming problems. From these additional formulations lower-bounds were obtained for the PFHPM. These values were used to validate a specialized Variable Neighborhood Search (VNS) algorithm, proposed to solve the PFHPM. This algorithm provided good quality solutions for the PFHPM, solving artificial generated instances from a Monte Carlo Simulation and real data instances, even with limited computational resources. Statistical analyses presented in this work suggest that the new algorithm and model, the PFHPM, can recover more accurately the original category structures related to heterogeneous individual’s perceptions than the original model and algorithm, the HPM. Finally, an illustrative application of the PFHPM is presented, as well as some insights about some new possibilities for it, extending the new model to fuzzy environments

Cooperative routing for collision minimization in wireless sensor networks

Cooperative communication has gained much interest due to its ability to exploit the broadcasting nature of the wireless medium to mitigate multipath fading. There has been considerable amount of research on how cooperative transmission can improve the performance of the network by focusing on the physical layer issues. During the past few years, the researchers have started to take into consideration cooperative transmission in routing and there has been a growing interest in designing and evaluating cooperative routing protocols. Most of the existing cooperative routing algorithms are designed to reduce the energy consumption; however, packet collision minimization using cooperative routing has not been addressed yet. This dissertation presents an optimization framework to minimize collision probability using cooperative routing in wireless sensor networks. More specifically, we develop a mathematical model and formulate the problem as a large-scale Mixed Integer Non-Linear Programming problem. We also propose a solution based on the branch and bound algorithm augmented with reducing the search space (branch and bound space reduction). The proposed strategy builds up the optimal routes from each source to the sink node by providing the best set of hops in each route, the best set of relays, and the optimal power allocation for the cooperative transmission links. To reduce the computational complexity, we propose two near optimal cooperative routing algorithms. In the first near optimal algorithm, we solve the problem by decoupling the optimal power allocation scheme from optimal route selection. Therefore, the problem is formulated by an Integer Non-Linear Programming, which is solved using a branch and bound space reduced method. In the second near optimal algorithm, the cooperative routing problem is solved by decoupling the transmission power and the relay node se- lection from the route selection. After solving the routing problems, the power allocation is applied in the selected route. Simulation results show the algorithms can significantly reduce the collision probability compared with existing cooperative routing schemes.

How effective are heuristic solutions for electricity planning in developing countries

Acknowledgement The first author would like to acknowledge the University of Aberdeen and the Henderson Economics Research Fund for funding his PhD studies in the period 2011-2014 which formed the basis for the research presented in this paper. The first author would also like to acknowledge the Macaulay Development Trust which funds his postdoctoral fellowship with The James Hutton Institute, Aberdeen, Scotland. The authors thank two anonymous referees for valuable comments and suggestions on earlier versions of this paper. All usual caveats apply

Optimal Capital Requirements in Financial Networks with Fire Sales

I explore and analyze a problem of finding the socially optimal capital requirements for financial institutions considering two distinct channels of contagion: direct exposures among the institutions, as represented by a network and fire sales externalities, which reflect the negative price impact of massive liquidation of assets.These two channels amplify shocks from individual financial institutions to the financial system as a whole and thus increase the risk of joint defaults amongst the interconnected financial institutions; this is often referred to as systemic risk. In the model, there is a trade-off between reducing systemic risk and raising the capital requirements of the financial institutions. The policymaker considers this trade-off and determines the optimal capital requirements for individual financial institutions. I provide a method for finding and analyzing the optimal capital requirements that can be applied to arbitrary network structures and arbitrary distributions of investment returns.

In particular, I first consider a network model consisting only of direct exposures and show that the optimal capital requirements can be found by solving a stochastic linear programming problem. I then extend the analysis to financial networks with default costs and show the optimal capital requirements can be found by solving a stochastic mixed integer programming problem. The computational complexity of this problem poses a challenge, and I develop an iterative algorithm that can be efficiently executed. I show that the iterative algorithm leads to solutions that are nearly optimal by comparing it with lower bounds based on a dual approach. I also show that the iterative algorithm converges to the optimal solution.

Finally, I incorporate fire sales externalities into the model. In particular, I am able to extend the analysis of systemic risk and the optimal capital requirements with a single illiquid asset to a model with multiple illiquid assets. The model with multiple illiquid assets incorporates liquidation rules used by the banks. I provide an optimization formulation whose solution provides the equilibrium payments for a given liquidation rule.

I further show that the socially optimal capital problem using the ``socially optimal liquidation" and prioritized liquidation rules can be formulated as a convex and convex mixed integer problem, respectively. Finally, I illustrate the results of the methodology on numerical examples and

discuss some implications for capital regulation policy and stress testing.

Effektiviseringsmöjligheter avseende fyllnadsgrad : En jämförande analys mellan nuläge och optimerat resultat

The study aims to provide information on efficiency opportunities on SCA's northbound cassettes. It has been made by examining the capacity utilization rate on the northbound cassettes on SCA's vessels for a period of two weeks. The cargo loaded in the ports of Rotterdam and Sheerness consists of external cargo of varying shape. The cargo is shipped northbound to Holmsund and Sundsvall. Measurements have been made on the cargo to the final destinations Sundsvall, Holmsund and Finland. The measurements have been used in a mathematical optimization model created to optimize the loading of the cassettes. The model is based on placing boxes in a grid where the boxes that are placed representing the cargo and the grids representing the cassettes. The aim of the model is to reduce the number of cassettes and thereby increase the capacity utilization rate. The study resulted in an increase in capacity utilization rate for both area and volume to all destinations. The overall improvement for all cassettes examined resulted in an increase in the area capacity utilization rate by 9.02 percentage points and 5.72 percentage points for the volume capacity utilization rate. It also resulted in a decrease of 22 cassettes in total on the four voyages that were examined which indicate that there are opportunities to improve the capacity utilization rate. The study also shows that the model can be used as a basis for similar problems.

Schedulazione delle rotte marittime nel settore ortofrutticolo. Modelli e Metodi

Il trasporto marittimo è una delle modalità più utilizzate soprattutto per la movimentazione di grandi volumi di prodotti tra i continenti in quanto è a basso costo, sicuro e meno inquinante rispetto ad altri mezzi di movimentazione. Ai giorni nostri è responsabile di circa l’80% del commercio globale (in volume di carichi trasportati). Il settore del trasporto marittimo ha avuto una lunga tradizione di pianificazione manuale effettuata da progettisti esperti.
 L’obiettivo principale di questa trattazione è stato quello di implementare un modello matematico lineare (MILP, Mixed-Integer Linear Programming Model) per l’ottimizzazione delle rotte marittime nell’ambito del mercato orto-frutticolo che si sviluppa nel bacino del Mediterraneo (problema di Ship-Scheduling). Il modello fornito in questa trattazione è un valido strumento di supporto alle decisioni che può utilizzare uno spedizioniere nell’ambito della pianificazione delle rotte marittime della flotta di navi in suo possesso. Consente di determinare l’insieme delle rotte ottimali che devono essere svolte da un insieme di vettori al fine di massimizzare il profitto complessivo dello spedizioniere, generato nell’arco di tempo considerato. Inoltre, permette di ottenere, per ogni nave considerata, la ripartizione ottimale della merce (carico ottimale).

Discrete-event Simulation and Optimization to Improve the Performance of a Healthcare System

Thesis (Ph.D.)--University of Washington, 2016-08

Exact solutions to the short sea shipping distribution problem

Short sea shipping has several advantages over other means of transportation, recognized by EU members. The maritime transportation could be dealt like a combination of two well-known problems: the container stowage problem and routing planning problem. The integration of these two well-known problems results in a new problem CSSRP (Container stowage and ship routing problem) that is also an hard combinatorial optimization problem. The aim of this work is to solve the CSSRP using a mixed integer programming model. It is proved that regardless the complexity of this problem, optimal solutions could be achieved in a reduced computational time. For testing the mathematical model some problems based on real data were generated and a sensibility analysis was performed.

The suppliers selection problem: a case study

The effective supplier evaluation and purchasing processes are of vital importance to business organizations, making the suppliers selection problem a fundamental key issue to their success. We consider a complex supplier selection problem with multiple products where minimum package quantities, minimum order values related to delivery costs, and discounted pricing schemes are taken into account. Our main contribution is to present a mixed integer linear programming (MILP) model for this supplier selection problem. The model is used to solve several examples including three real case studies from an electronic equipment assembly company.

Airport ground movement

Worldwide air traffic tends to increase and for many airports it is no longer an op-tion to expand terminals and runways, so airports are trying to maximize their op-erational efficiency. Many airports already operate near their maximal capacity. Peak hours imply operational bottlenecks and cause chained delays across flights impacting passengers, airlines and airports. Therefore there is a need for the opti-mization of the ground movements at the airports. The ground movement prob-lem consists of routing the departing planes from the gate to the runway for take-off, and the arriving planes from the runway to the gate, and to schedule their movements. The main goal is to minimize the time spent by the planes during their ground movements while respecting all the rules established by the Ad-vanced Surface Movement, Guidance and Control Systems of the International Civil Aviation. Each aircraft event (arrival or departing authorization) generates a new environment and therefore a new instance of the Ground Movement Prob-lem. The optimization approach proposed is based on an Iterated Local Search and provides a fast heuristic solution for each real-time event generated instance granting all safety regulations. Preliminary computational results are reported for real data comparing the heuristic solutions with the solutions obtained using a mixed-integer programming approach.

Train scheduling and rolling stock assignment in high speed trains

The Train Timetabling Problem (TTP) has been widely studied for freight and passenger rail systems. A lesser effort has been devoted to the study of high-speed rail systems. A modeling issue that has to be addressed is to model departure time choice of passengers on railway services. Passengers who use these systems attempt to travel at predetermined hours due to their daily life necessities (e.g., commuter trips). We incorporate all these features into TTP focusing on high-speed railway systems. We propose a Rail Scheduling and Rolling Stock (RSch-RS) model for timetable planning of high-speed railway systems. This model is composed of two essential elements: i) an infrastructure model for representing the railway network: it includes capacity constraints of the rail network and the Rolling-Stock constraints; and ii) a demand model that defines how the passengers choose the departure time. The resulting model is a mixed-integer programming model which objective function attempts to maximize the profit for the rail operator

Exact solutions for the agricultural and the two-dimensional packing problems

Objectives and study method: The objective of this study is to develop exact algorithms that can be used as management tools for the agricultural production planning and to obtain exact solutions for two of the most well known twodimensional packing problems: the strip packing problem and the bin packing problem. For the agricultural production planning problem we propose a new hierarchical scheme of three stages to improve the current agricultural practices. The objective of the first stage is to delineate rectangular and homogeneous management zones into the farmer’s plots considering the physical and chemical soil properties. This is an important task because the soil properties directly affect the agricultural production planning. The methodology for this stage is based on a new method called “Positions and Covering” that first generates all the possible positions in which the plot can be delineated. Then, we use a mathematical model of linear programming to obtain the optimal physical and chemical management zone delineation of the plot. In the second stage the objective is to determine the optimal crop pattern that maximizes the farmer’s profit taken into account the previous management zones delineation. In this case, the crop pattern is affected by both management zones delineation, physical and chemical. A mixed integer linear programming is used to solve this stage. The objective of the last stage is to determine in real-time the amount of water to irrigate in each crop. This stage takes as input the solution of the crop planning stage, the atmospheric conditions (temperature, radiation, etc.), the humidity level in plots, and the physical management zones of plots, just to name a few. This procedure is made in real-time during each irrigation period. A linear programming is used to solve this problem. A breakthrough happen when we realize that we could propose some adaptations of the P&C methodology to obtain optimal solutions for the two-dimensional packing problem and the strip packing. We empirically show that our methodologies are efficient on instances based on real data for both problems: agricultural and two-dimensional packing problems. Contributions and conclusions: The exact algorithms showed in this study can be used in the making-decision support for agricultural planning and twodimensional packing problems. For the agricultural planning problem, we show that the implementation of the new hierarchical approach can improve the farmer profit between 5.27% until 8.21% through the optimization of the natural resources. An important characteristic of this problem is that the soil properties (physical and chemical) and the real-time factors (climate, humidity level, evapotranspiration, etc.) are incorporated. With respect to the two-dimensional packing problems, one of the main contributions of this study is the fact that we have demonstrate that many of the best solutions founded in literature by others approaches (heuristics approaches) are the optimal solutions. This is very important because some of these solutions were up to now not guarantee to be the optimal solutions.