Search

The Vehicle Routing Problem with Loading Constraints (VRPLC) is strongly related to real life applications in distribution logistics. It addresses the simultaneous loading and routing of vehicles, which are two crucial activities in transportation. Since treating these operations separately may result in impractical solutions, the development of applications for VRPLCs has gained the attention of researchers in recent years. Several heuristic methods have been proposed, but they consider only a limited group of practical characteristics that arise in real world situations. This study proposes a hybrid heuristic method based on the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and the Clarke and Wright Savings algorithm, to solve a VRPLC with several loading and routing constraints that have not been considered simultaneously before. Experimental results show that the proposed procedure produces competitive solutions in short processing times. Lastly, the impact of the added operational constraints is also analyzed.

This paper addresses the stochastic permutation flow shop problem (SPFSP) in which the stochastic parameters are the processing times. This allows the modeling of setups and machine breakdowns. Likewise, it is proposed a multi-objective greedy randomized adaptive search procedure (GRASP) coupled with Monte-Carlo Simulation to obtain expected makespan and expected tardiness. To manage the bi-objective function, a sequential combined method is considered in the construction phase of the meta-heuristic. Moreover, the local Search combines 2-optimal interchanges with a Pareto Archived Evolution Strategy (PAES) to obtain the Pareto front. Also, some Taillard benchmark instances of deterministic permutation flow shop problem were adapted in order to include the variation in processing times. Accordingly, two coefficients of variation (CVs) were tested: one depending on expected processing times values defined as twice the expected processing time of a job, and a fixed value of 0.25. Thus, the computational results on benchmark instances show that the variable CV provided lower values of the expected makespan and tardiness, while the con-stant CV presented higher expected measures. The computational results present insights for further analysis on the behavior of stochastic scheduling problems for a better approach in real-life scenarios at industrial and service systems.

Patient Bed Assignment (PBA) consists of assigning patients to hospital beds according to specific requirements such as patient diagnosis, equipment requirements, age and gender policies, among others. We worked in conjunction with the Hospital Universitario San Ignacio (HUSI) with the goal of designing an application to support decision-making during the bed assignment process. We introduced a mathematical model for the PBA. We used Analytic Hierarchy Process (AHP) to determine the weights attributed to each part of the objective function. Due to the long execution time required, we used a Greedy Algorithm and Tabu Search (TS) to optimize the match between the patient’s requirements and the characteristics of the assigned bed. To test the algorithms, we created 15 test instances of various sizes. The results showed that the gap between the value of the objective function resulting from using the Greedy/TS in comparison with the optimal solution is on average 6.2%. Also, the TS takes 84% less time than the MILP for medium and large instances. We collected data from real life instances and compared the actual method with the designed metaheuristic. On average, the value of the objective function resulting from using the proposed Greedy/Tabu algorithm is 8.6% higher.

Nowadays, industries cope with a wide range of situations and/or perturbations that endanger the manufacturing productivity. Traditionally, manufacturing control systems are responsible for managing the manufacturing scheduling and execution, as these have the capability of maintaining the production operations regardless of a given perturbation. Still, the challenge of these systems is to achieve an optimal performance after the perturbations occur. For this reason, manufacturing control systems must incorporate a mechanism with intelligent capabilities to look for optimal performance and operation reactivity regardless of any scenario. This paper proposes a generic control strategy for a manufacturing control system for piloting the execution of a dynamic scheduling problem, considering a new job arrival as the manufacturing perturbation. The study explores a predictive-reactive approach that couples a genetic algorithm for the predictive scheduling and an adaptive genetic algorithm for reactivity control aiming to minimize the weighted tardiness in a dynamic manufacturing scenario. The results obtained from this proposal verify that the effectiveness was improved by using adaptive metaheuristic in a dynamic scheduling problem, considering absorbing the degradation caused by the perturbation.

This work studies the scheduling of elective procedures, with stochastic durations, in surgery rooms. Given a set of rooms with limited availability and a set of procedures, it must be decided in which room and when each procedure will be performed. The problem’s objectives are to maximize the use of the operating rooms and to minimize the delays in starting the scheduled surgeries. A simulation-optimization approach is proposed. First, procedures’ durations are modeled as random variables and a set of test percentiles (i.e. it is assumed that all surgeries will last as many minutes as the 75th percentile of its probability density function) is selected. Subsequently, using these durations as a parameter, a greedy randomized adaptive search procedure (GRASP) is run. Consequently, as many solutions as selected test percentiles are generated. Finally, a Monte Carlo simulation is used to estimate three indicators: i) rooms utilization, ii) percentage of surgeries that had delays, and iii) average delay time of scheduled surgeries. The technique was tested by solving the elective procedures scheduling problem in a high-complexity hospital in Bogota. This hospital has 19 operating rooms and 35,000 surgeries performed annually. Currently, the scheduling process is manual. The simulation-optimization proposed approach allowed to determine the relation between utilization rate and delays in the service. As the occupation percentage increases, delay times also augment, implying a reduction of the service level. An average reduction of 5% in delay times entails a reduction between 3% and 9% of operating room occupancy.

Many supply chains are composed of producers, suppliers, carriers, and customers. These agents must be coordinated to reduce waste and lead times. Production and distribution are two essential phases in most supply chains. Hence, improving the coordination of these phases is critical. This paper studies a combined hybrid flow-shop and vehicle routing problem. The production phase is modeled as a hybrid flow-shop configuration. In the second phase, the produced jobs have to be delivered to a set of customers. The delivery is carried out in batches of products, using vehicles with a limited capacity. With the objective of minimizing the service time of the last customer, we propose a biased-randomized variable neighborhood descent algorithm. Different test factors, such as the use of alternative initial solutions, solution representations, and loading strategies, are considered and analyzed.

This paper considers a hybrid flowshop scheduling problem (HFSP). Since this problem is NP-hard, most of literature has been centred on the analysis of meta-heuristics and hybridised procedures. However, intelligent manufacturing systems in actual industrial practices mostly prefer the use of simple algorithms. The greedy randomised adaptive search procedure (GRASP) is among the simplest approximation algorithms providing good results when solving hard combinatorial optimisation problems that currently exist in literature. The objective is to propose a GRASP to solve the classical HFSP under the optimisation of different objectives. The goal is not to solve a multi-objective problem, instead to design a solution procedure that performs well under various optimisation criteria. This performance is analysed through a set of computational experiments using well-known data-sets from the literature. The proposed GRASP obtains satisfactory results in comparison with traditional dispatching rules and can...

Modern production systems require multiple manufacturing centers—usually distributed among different locations—where the outcomes of each center need to be assembled to generate the final product. This paper discusses the distributed assembly permutation flow-shop scheduling problem, which consists of two stages: the first stage is composed of several production factories, each of them with a flow-shop configuration; in the second stage, the outcomes of each flow-shop are assembled into a final product. The goal here is to minimize the makespan of the entire manufacturing process. With this objective in mind, we present an efficient and parameter-less algorithm that makes use of a biased-randomized iterated local search metaheuristic. The efficiency of the proposed method is evaluated through the analysis of an extensive set of computational experiments. The results show that our algorithm offers excellent performance when compared with other state-of-the-art approaches, obtaining several new bestsolutions.

This paper proposes a hybridized simheuristic approach that couples a greedy randomized adaptive search procedure (GRASP), a Monte Carlo simulation, a Pareto archived evolution strategy (PAES), and an analytic hierarchy process (AHP), in order to solve a multicriteria stochastic permutation flow shop problem with stochastic processing times and stochastic sequence-dependent setup times. For the decisional criteria, the proposed approach considers four objective functions, including two quantitative and two qualitative criteria. While the expected value and the standard deviation of the earliness/tardiness of jobs are included in the quantitative criteria to address a robust solution in a just-in-time environment, this approach also includes a qualitative assessment of the product and customer importance in order to appraise a weighted priority for each job. An experimental design was carried out in several study instances of the flow shop problem to test the effects of the processing times and sequence-dependent setup times, obtained through lognormal and uniform probability distributions with three levels of coefficients of variation, settled as 0.3, 0.4, and 0.5. The results show that both probability distributions and coefficients of variation have a significant effect on the four decision criteria selected. In addition, the analytical hierarchical process makes it possible to choose the best sequence exhibited by the Pareto frontier that adjusts more adequately to the decision-makers’ objectives.

11 páginas This paper presents a comparison of several well-known dispatching rules hybridised with Monte Carlo simulation to solve the Permutation Flow Shop Scheduling Problem with stochastic processing times. The aim of the paper is to show the importance of making an accurate probability distribution fitting of the uncertain parameter for adequate decision-making, especially if a robust schedule is desired. An experimental design was carried out to test the performance of 13 dispatching rules with three probability distributions and different coefficients of variation for the processing times. Experimental results were obtained for the expected mean and the standard deviation of five objective functions: makespan, flowtime, tardiness, maximum tardiness and tardy jobs. Results show that dispatching rules behave differently for mean and standard deviation regardless of the objective function. Hence, selected dispatching rules must be different if the goal is obtaining a robust schedule or to minimise the expected mean of a specific objective. Additionally, performance of dispatching rules depends on the coefficients of variation of processing times. These results demonstrate the importance of collecting enough and precise information of uncertain parameters to determine the probability distribution that fits the best.

The aim of this paper is to present a simheuristic approach that obtains robust schedules for a multi-objective permutation flow shop problem with stochastic processing times. In fact, this approach minimizes the expected tardiness and standard deviation of tardiness, as a efficiency and a robustness measure for the stated problem. The simheuristic algorithm hybridize the Tabu Search metaheuristic and the Pareto Archived Evolution Strategy algorithm with a Monte Carlo Simulation process. At first, this approach is tested in 540 benchmarked instances for the deterministic case. It uses a zero-standard-deviation strategy to show the competitiveness compared with other implemented tabu search algorithms. Afterwards, two experimental designs are carried out, with the same 540 instances, where two factors of interest are considered, such as the probability distribution and coefficient of variation of processing times. The probability distributions used were the lognormal and uniform distributions, and three coefficients of variation (0.3, 0.4, and 0.5). Results show that both probability distributions and coefficients of variation have a significant effect in the objective functions, showing the importance of an accurate fitting of probability distributions of the parameter under uncertainty. In addition, these results evidence that the usage of deterministic methods in presence of random events are not desirable or recommended. Finally, the simheuristic was implemented to solve the scheduling problem in an optical laboratory showing better results for expected tardiness and standard deviation of tardiness in comparison with company schedules.

Modern manufacturing systems are composed of several stages. We consider a manufacturing environment in which different parts of a product are completed in a first stage by a set of distributed flowshop lines, and then assembled in a second stage. This is known as the distributed assembly permutation flowshop problem (DAPFSP). This paper studies the stochastic version of the DAPFSP, in which processing and assembly times are random variables. Besides minimizing the expected makespan, we also discuss the need for considering other measures of statistical dispersion in order to account for risk. A hybrid algorithm is proposed for solving this NP -hard and stochastic problem. Our approach integrates biased randomization and simulation techniques inside a metaheuristic framework. A series of computational experiments contribute to illustrate the effectiveness of our approach.

El Departamento de Cirugía genera una buena parte de los ingresos de un hospital. Este estudio evalúa la variabilidad en la programación de las cirugías y cómo esta atenta contra la eficiencia del servicio. Este estudio implementó un algoritmo para la generación de dos programaciones que luego fueron comparadas con la realizada manualmente en un hospital en Colombia. Las dos programaciones generadas se diferencian entre sí al incluir o no las máximas desviaciones en los tiempos de duración de las cirugías, asumiendo que estas son causadas por factores externas al proceso y pueden ser eliminadas. Los resultados muestran que al emplear un algoritmo automático para programar las cirugías, podrían mejorarse el tiempo de respuesta y la utilización de las salas. Aún más, se pudo concluir que la variabilidad asociada a la programación manual tiene un mayor impacto que la asociada a otros factores en los indicadores de desempeño del servicio.