No description available.

No description available.

Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

This research aims to improve the performance of the service of a Chemotherapy Treatment Unit by reducing the waiting time of patients within the unit. In order to fulfill the objective, initially, the chemotherapy treatment unit is deduced as an identical parallel machines scheduling problem with unequal release time and single resource. A mathematical model is developed to generate the optimum schedule. Afterwards, a Tabu search (TS) algorithm is developed. The performance of the TS algorithm is evaluated by comparing results with the mathematical model and the best results of benchmark problems reported in the literature. Later on, an additional resource is considered which converted the problem into a dual resources scheduling problem. Three approaches are proposed to solve this problem; namely, heuristics, a Tabu search algorithm with heuristic (TSHu), and Tabu search algorithm for dual resources (TSD).

This research aims to improve the performance of the service of a Chemotherapy Treatment Unit by reducing the waiting time of patients within the unit. In order to fulfill the objective, initially, the chemotherapy treatment unit is deduced as an identical parallel machines scheduling problem with unequal release time and single resource. A mathematical model is developed to generate the optimum schedule. Afterwards, a Tabu search (TS) algorithm is developed. The performance of the TS algorithm is evaluated by comparing results with the mathematical model and the best results of benchmark problems reported in the literature. Later on, an additional resource is considered which converted the problem into a dual resources scheduling problem. Three approaches are proposed to solve this problem; namely, heuristics, a Tabu search algorithm with heuristic (TSHu), and Tabu search algorithm for dual resources (TSD).

The purpose of this thesis is to develop a heuristic solution for the static problem of resequencing unblocked vehicles as a part of an ongoing research project at Daimler AG. The target client of this project is Mercedes-Benz Cars. An unblocked vehicle is defined as a vehicle that for some reason could not be processed in its given time slot but at a later point in time needs to be inserted into the production sequence. Work overload is defined as work that the worker is unable to finish prior to reaching the station border. The resequencing problem can be described as finding new positions for a set of unblocked vehicles in a sequence of previously not blocked vehicles, such that the new sequence containing the previously not blocked vehicles and the additional unblocked vehicles causes as little work overload as possible. A decision has to be made in real-time, forcing the solution method to return a solution within a cycle time. Today, Mercedes-Benz Cars uses the sequencing approach “car sequencing”. This approach relies on so called spacing constraints, which basically means, trying to distribute work intensive vehicles as evenly as possible over the planning horizon and thereby enabling a hopefully smooth production. The car sequencing approach needs limited information. The difficulty is to find spacing constraints that fits the high level of product customization characterizing a modern car manufacturer. To overcome these difficulties, a new approach is being considered, namely the mixed-model sequencing, which takes more detailed data into account than the car sequencing approach but on the other hand is more costly in terms of computation. To this end, a simple but promising tabu search scheme was developed, that for many instances was able to find the optimal solution in less than 30 seconds of computing time and that also clearly outperformed all benchmark heuristics.

We use models to simulate the real world mainly for prediction purposes. However, since any model is a simplification of reality, there remains a great deal of uncertainty even after the calibration of model parameters. The model’s identifiability of realistic model parameters becomes questionable when the watershed of interest is small, and its time of concentration is shorter than the computational time step of the model. To improve the discovery of more reliable and more realistic sets of model parameters instead of mathematical solutions, a new algorithm is needed. This algorithm should be able to identify mathematically inferior but more robust solutions as well as to take samples uniformly from high-dimensional search spaces for the purpose of uncertainty analysis. Various watershed configurations were considered to test the Soil and Water Assessment Tool (SWAT) model’s identifiability of the realistic spatial distribution of land use, soil type, and precipitation data. The spatial variability in small watersheds did not significantly affect the hydrographs at the watershed outlet, and the SWAT model was not able to identify more realistic sets of spatial data. A new populationbased heuristic called the Isolated Speciation-based Particle Swarm Optimization (ISPSO) was developed to enhance the explorability and the uniformity of samples in high-dimensional problems. The algorithm was tested on seven mathematical functions and outperformed other similar algorithms in terms of computational cost, consistency, and scalability. One of the test functions was the Griewank function, whose number of minima is not well defined although the function serves as the basis for evaluating multi-modal optimization algorithms. Numerical and analytical methods were proposed to count the exact number of minima of the Griewank function within a hyperrectangle. The ISPSO algorithm was applied to the SWAT model to evaluate the performance consistency of optimal solutions and perform uncertainty analysis in the Generalized Likelihood Uncertainty Estimation (GLUE) framework without assuming a statistical structure of modeling errors. The algorithm successfully found hundreds of acceptable sets of model parameters, which were used to estimate their prediction limits. The uncertainty bounds of this approach were comparable to those of the typical GLUE approach.

No-wait scheduling problem refers to the set of problems in which a number of jobs are available for processing on a number of machines with the added constraint that there should be no waiting time between consecutive operations of the jobs. It is well-known that most of the no-wait scheduling problems are strongly NP-hard. Moreover, no-wait scheduling problems have numerous real-life applications. This thesis studies a wide range of no-wait scheduling problems, along with side constraints that make such problems more applicable. First, 2-machine no-wait flow shop problem is studied. Afterwards, setup times and single server constraints are added to this problem in order to make it more applicable. Then, job shop version of this problem is further researched. Analytical results for both of these problems are presented; moreover, efficient algorithms are developed and applied to large instances of these problems. Afterward, general no-wait flow shop problem (NWFS) is the focus of the thesis. First, the NWFS is studied; mathematical models as well as metaheuristics are developed for NWFS. Then, setup times are added to NWFS in order to make the problem more applicable. Finally, the case of sequence dependent setup times is further researched. Efficient algorithms are developed for both problems. Finally, no-wait job shop (NWJS) problem is studied. Literature has proposed different methods to solve NWJS; the most successful approaches decompose the problem into a timetabling sub-problem and a sequencing sub-problem. Different sequencing and timetabling algorithms are developed to solve NWJS. This thesis provides insight to several no-wait scheduling problems. A number of theorems are discussed and proved in order to find the optimum solution of no-wait problems with special characteristics. For the problems without such characteristics, mathematical models are developed. Metaheuristics are utilized to deal with large-instances of NP-hard problems. Computational results show that the developed methods in this thesis are very effective and efficient compared to the competitive methods available in the literature.

No-wait scheduling problem refers to the set of problems in which a number of jobs are available for processing on a number of machines with the added constraint that there should be no waiting time between consecutive operations of the jobs. It is well-known that most of the no-wait scheduling problems are strongly NP-hard. Moreover, no-wait scheduling problems have numerous real-life applications. This thesis studies a wide range of no-wait scheduling problems, along with side constraints that make such problems more applicable. First, 2-machine no-wait flow shop problem is studied. Afterwards, setup times and single server constraints are added to this problem in order to make it more applicable. Then, job shop version of this problem is further researched. Analytical results for both of these problems are presented; moreover, efficient algorithms are developed and applied to large instances of these problems. Afterward, general no-wait flow shop problem (NWFS) is the focus of the thesis. First, the NWFS is studied; mathematical models as well as metaheuristics are developed for NWFS. Then, setup times are added to NWFS in order to make the problem more applicable. Finally, the case of sequence dependent setup times is further researched. Efficient algorithms are developed for both problems. Finally, no-wait job shop (NWJS) problem is studied. Literature has proposed different methods to solve NWJS; the most successful approaches decompose the problem into a timetabling sub-problem and a sequencing sub-problem. Different sequencing and timetabling algorithms are developed to solve NWJS. This thesis provides insight to several no-wait scheduling problems. A number of theorems are discussed and proved in order to find the optimum solution of no-wait problems with special characteristics. For the problems without such characteristics, mathematical models are developed. Metaheuristics are utilized to deal with large-instances of NP-hard problems. Computational results show that the developed methods in this thesis are very effective and efficient compared to the competitive methods available in the literature.