Search

The Master Surgery Scheduling Problem (MSSP) can be described as a timetabling problem involving assigning surgery groups to operating theatre (OT) time slots. Previous MSSP optimization models considered throughput, waiting measures, resource utilization, costs, and schedule assignment objectives, but have overlooked consecutive days assignment preferences and surgical equipment-sharing limitations. Furthermore, previous works utilize greedy constructive heuristics to produce solutions, which increases quality but decreases feasibility. Our prior study demonstrated that the saturation degree heuristic enhances feasibility by considering assignment difficulty during event selection. However, its impact on solution quality remained unexplored. Therefore, this study proposes an improved saturation degree-based constructive heuristic that integrates objective function value for event selection to increase both quality and feasibility. The algorithm sorts surgery groups by unit scores, prioritizing higher assignment difficulty and objective value. The highest-scoring group is assigned to its feasible slot with the highest slot score. If no feasible slots exist, the repair mechanism vacates the slot with the highest swap score, which prioritizes lower assignment difficulty and objective value. A new mathematical model is also formulated, incorporating novel objectives regarding consecutive days assignment preference and surgical equipment-sharing limitations. Using real-world data from Hospital Canselor Tuanku Muhriz, the proposed algorithm is evaluated considering repair mechanism usage for feasibility and objective function value for quality. The algorithm is benchmarked against greedy, random, regret-based, and saturation degree-based constructive heuristics. Our algorithm achieved a 14.63% improvement in feasibility compared to the original variant. Its objective function value is over two times better than the closest competitor and 2.6 times superior to the original variant. Comparison with the hospital’s actual plan demonstrates competitive objective function value and a more balanced waiting time distribution among surgical groups. Our study showcases that a saturation degree-based constructive heuristic considering objective function value has increased solution quality while maintaining feasibility.

The study extends the traditional pick-up and delivery problems (PDPs) to address the specific challenges of urban logistics and electric vehicle (EV) adoption. These challenges include the limited range of EVs, energy consumption along the route, and uncertainty in traffic conditions. To overcome the limited range of EVs, the study includes battery swapping stations to ensure sufficient energy to complete delivery routes. Vehicle energy consumption is considered to reduce range anxiety and optimize energy use. The study also considers the unpredictability of traffic conditions that affect energy consumption and delivery schedules. To address these concerns, the study proposes an approximate Quadratic Chance-Constrained Mixed-Integer Programming (QC-MIP) model with a linear approximation, a constructive heuristic and a meta-heuristic. These quantitative models incorporate comprehensive EV energy estimation approaches, enabling more accurate energy predictions. The proposed approaches provide valuable insights and strategies for improving energy efficiency and delivery performance in urban logistics environments. [ABSTRACT FROM AUTHOR]

Energy-efficient scheduling is highly necessary for energy-intensive industries, such as glass, mould or chemical production. Inspired by a real-world glass-ceramics production process, this paper investigates a bi-criteria energy-efficient two-stage hybrid flow shop scheduling problem, in which parallel machines with eligibility are at stage 1 and a batch machine is at stage 2. The performance measures considered are makespan and total energy consumption. Time-of-use (TOU) electricity prices and different states of machines (working, idle and turnoff) are integrated. To tackle this problem, a mixed integer programming (MIP) is formulated, based on which an augmented ε-constraint (AUGMECON) method is adopted to obtain the exact Pareto front. A problem-tailored constructive heuristic method with local search strategy, a bi-objective tabu search algorithm and a bi-objective ant colony optimisation algorithm are developed to deal with medium- and large-scale problems. Extensive computational experiments are conducted, and a real-world case is solved. The results show effectiveness of the proposed methods, in particular the bi-objective tabu search. [ABSTRACT FROM AUTHOR]

As the first and the most time consuming step of product recovery, disassembly is described as the systematic separation of constituent parts from end-of-life products through a series of operations. In this context, designing and balancing disassembly lines are critical in terms of the efficiency of product recovery. Recent research on disassembly line balancing (DLB) has focused on classical stations where only one worker is allocated. However, such a line results in larger space requirement and longer disassembly lead time. In this paper, disassembly line balancing problem (DLBP) with multi-manned stations is introduced to the relevant literature as a solution to overcome these disadvantages. A mixed integer linear programming (MILP) model and two novel framework heuristic algorithms are developed to minimise the number of workers and workstations. MILP model has been applied to a dishwasher disassembly system. The application results indicate the superiority of establishing multi-manned stations over classical disassembly system design with single-worker stations with shorter disassembly lead time (80.9%) and line length (60.2%). Moreover, the proposed heuristics have been compared on newly generated test problems (instances) for DLBP. The results validate that the heuristics provide acceptable solutions in a reasonable amount of time even for large-sized problems. [ABSTRACT FROM AUTHOR]

Academic institutions may be edging towards a global uncertainty, recession, and a string of financial difficulties. An effective course timetabling is one of managerial strategies to optimise the operating costs and resource utilisation. This paper presents the first application of firefly algorithm (FA) and its modifications and hybridisations for solving real-world course timetabling problem. A novel bi-objective firefly algorithm (BOFA) with Pareto dominance approach was developed for optimising the operating costs and resource utilisation. Random key technique was applied for adapting the continuous firefly movement to solve discrete timetabling problem. Five constructive heuristics were additionally embedded into the BOFA for initialising feasible timetables. Computational experiments were sequentially conducted using eleven problem instances obtained from a collaborating university. It was found that the proposed hybridisation outperformed particle swarm optimisation, the classical FA, and modified FA (MFA), in terms of the quality of the timetables obtained, computational times and convergent speed. The proposed hybrid bi-objective FA (HBOFA) yielded better Pareto frontiers than the conventional BOFA with less computational times for all problem instances. [ABSTRACT FROM AUTHOR]

Increasing global energy consumption, large variations in its cost and the environmental degradation effects are good reasons for the manufacturing industries to become greener. Green shop floor scheduling is increasingly becoming a vital factor in the sustainable manufacturing. In this paper, a green permutation flowshop scheduling problem with sequence-dependent setup times is studied. Two objectives are considered including minimisation of makespan as a measure of service level and minimisation of total energy consumption as a measure of environmental sustainability. We extend a bi-objective mixed-integer linear programming model to formulate the stated problem. We develop a constructive heuristic algorithm to solve the model. The constructive heuristic algorithm includes iterated greedy (CHIG) and local search (CHLS) algorithms. We develop an efficient energy-saving method which decreases energy consumption, on average, by about 15%. To evaluate the effectiveness of the constructive heuristic algorithm, we compare it with the famous augmented ϵ-constraint method using various small-sized and large-sized problems. The results confirm that the heuristic algorithm obtains high-quality non-dominated solutions in comparison with the augmented ϵ-constraint method. Also, they show that the CHIG outperforms the CHLS. Finally, this paper follows a case-study, with in-depth analysis of the model and the constructive heuristic algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a new heuristic algorithm tailored to solve large instances of an NP-hard variant of the shortest path problem, denoted the cost-balanced path problem, recently proposed in the literature. The problem consists in finding the origin–destination path in a direct graph, having both negative and positive weights associated with the arcs, such that the total sum of the weights of the selected arcs is as close to zero as possible. At least to the authors' knowledge, there are no solution algorithms for facing this problem. The proposed algorithm integrates a constructive procedure and an improvement procedure, and it is validated thanks to the implementation of an iterated neighborhood search procedure. The reported numerical experimentation shows that the proposed algorithm is computationally very efficient. In particular, the proposed algorithm is most suitable in the case of large instances where it is possible to prove the existence of a perfectly balanced path and thus the optimality of the solution by finding a good percentage of optimal solutions in negligible computational time. [ABSTRACT FROM AUTHOR]

In this paper, flexible preventive maintenance (PM) activities are incorporated into two-stage assembly flow shop scheduling where m dedicated machines in the fabrication stage and one machine in the assembly stage. The operational status of each machine is described by a continuous variable, maintenance level. The maintenance level value is inversely proportional to the processing time. Once a PM activity is performed, this value will return to the initial value. Different from the PM at fixed predefined time intervals, flexible PM can be carried out at any time point, but the maintenance levels are not less than 0. Hence, a MILP model with maintenance level constraints is formulated to minimize the total completion time and maintenance time. Regarding the methods, a latest PM decision strategy is proposed to determine the execution time of PM activities. This new strategy is embedded into 15 constructive heuristics and 7 meta-heuristics (three variants of iterated local search, three variants of Q-learning-based ant colony system with local search and a Q-learning-based hyper-heuristics) to address this new problem. The final experimental analysis demonstrates the significance of the integrated model and the effectiveness of the proposed constructive heuristics and meta-heuristics. [ABSTRACT FROM AUTHOR]

Parallel tests contain different items but have the same measurement properties. They are administered at the same or different time slots and their measurement results must be comparable. The problem of automated parallel tests assembly is studied for a long time, and many (mostly improvement) heuristic solutions are proposed and elaborated in literature. Such approaches frequently suffer from algorithms of unpredictable execution time, forcing the methods to terminate execution when some time limit or solution quality is reached. This paper proposes an efficient method of polynomial complexity, as a complete solution to the automated parallel tests assembly problem. The method uses the idea of Nawaz, Enscore, and Ham constructive heuristic algorithm to reduce the number of examined permutations, originally exploited for solving the permutation flow-shop sequencing problem. We compared the experimental results of the proposed method with two methods based on improvement heuristics that solve the same problem formulation, simulated annealing and variable neighborhood search. The main advantages of the proposed method are predictable execution time and implementation simplicity. Achieved quality of assembled tests, combined with predictable test assembly execution time, may be of particular interest in cases when computational resources for test assembly and administering are overloaded. [ABSTRACT FROM AUTHOR]

This article studies the data collection task planning for a fixed-wing unmanned aerial vehicle (UAV) in forest fire monitoring. Multiple wireless-based detection nodes (DNs) are distributed in high-risk areas of the forest to monitor the surrounding environment. The task of UAV is to circularly fly to them and collect the environmental data. Because of the kinematic constraints of UAV and the effective communication range between UAV and DN, this problem can be generally regarded as a Dubins traveling salesman problem with neighborhood (DTSPN). A bi-level hybridization-based metaheuristic algorithm (BLHMA) is proposed for solving this problem. At the first level, differential evolution (DE) optimizes the continuous-valued communication positions and UAV headings by the population-based search. For the asymmetric traveling salesman problem (ATSP) corresponding to the combination of the positions and headings generated by DE, a constructive heuristic based on self-organized multi-agent competition (SOMAC) is proposed to determine the discrete collection sequence. By competitive iterations in such a cooperative way in DE, a high-quality data collection tour can be generated. At the second level, a local search based on multistage approximate gradient is proposed to further refine the positions and headings, which accelerates the convergence of the BLHMA. Referring to a real-world scene of forest fire monitoring, the simulation experiments are designed, and comparative results show that BLHMA can find significantly shorter data collection tours in most cases over three state-of-the-art algorithms. The proposed UAV data collection planning algorithm is conducive to the efficient execution of the forest fire monitoring data collection mission and the energy saving of UAV.

Purpose – This paper aims to define the class of fragment constructive heuristics used to compute feasible solutions for the traveling salesman problem (TSP) into edge-greedy and vertex-greedy subclasses. As these subclasses of heuristics can create subtours, two known methodologies for subtour elimination on symmetric instances are reviewed and are expanded to cover asymmetric problem instances. This paper introduces a third novel subtour elimination methodology, the greedy tracker (GT), and compares it to both known methodologies. Design/methodology/approach – Computational results for all three subtour elimination methodologies are generated across 17 symmetric instances ranging in size from 29 vertices to 5,934 vertices, as well as 9 asymmetric instances ranging in size from 17 to 443 vertices. Findings – The results demonstrate the GT is the fastest method for preventing subtours for instances below 400 vertices. Additionally, a distinction between fragment constructive heuristics and the subtour elimination methodology used to ensure the feasibility of resulting solutions enables the introduction of a new vertex-greedy fragment heuristic called ordered greedy. Originality/value – This research has two main contributions: first, it introduces a novel subtour elimination methodology. Second, the research introduces the concept of ordered lists which remaps the TSP into a new space with promising initial computational results.

This paper presents a new heuristic algorithm tailored to solve large instances of an NP-hard variant of the shortest path problem, denoted the cost-balanced path problem, recently proposed in the literature. The problem consists in finding the origin–destination path in a direct graph, having both negative and positive weights associated with the arcs, such that the total sum of the weights of the selected arcs is as close to zero as possible. At least to the authors’ knowledge, there are no solution algorithms for facing this problem. The proposed algorithm integrates a constructive procedure and an improvement procedure, and it is validated thanks to the implementation of an iterated neighborhood search procedure. The reported numerical experimentation shows that the proposed algorithm is computationally very efficient. In particular, the proposed algorithm is most suitable in the case of large instances where it is possible to prove the existence of a perfectly balanced path and thus the optimality of the solution by finding a good percentage of optimal solutions in negligible computational time.

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented. [ABSTRACT FROM PUBLISHER]

An active sonar system consists of a source emitting a sound pulse (ping) and a receiver listening to the reflection of the wave on a target, known as the echo. Such a system is further divided into two distinct configurations. The first one, named monostatic, is made up of a collocated source and receiver, while the second one, referred to as bistatic, is based on a non-collocated source and receiver. To this extent, a Multistatic Sonar Network (MSN) is thus comprised of a set of sources and receivers deployed across a given Area of Interest (AoI), which, taken pairwise, form sonar systems in monostatic and/or bistatic configuration. In this paper, we therefore propose an efficient two-phase greedy heuristic to solve the Area Coverage (AC) problem in the scope of MSNs, a special case of Wireless Sensor Networks (WSNs), while taking into account existing coastlines. For this problem, the objective is to determine the optimal spatial layout of the MSN, i.e. the one that maximize the overall coverage of the AoI with regard to a limited number of sensors and a given probabilistic detection model. Furthermore, we use a Mixed Integer Linear Program (MILP) from the literature as a reference for the numerical experiments conducted on a dataset of diversified instances. The latter were specifically derived from Digital Elevation Models (DEMs) of AoIs selected throughout the globe and in such a way as to encompass a wide spectrum of peculiar geometric situations. • Proposal of a first heuristic dealing with coastlines in multistatic sonar placement. • Taking into account binary and probabilistic models as well as the direct blast. • Creation of a benchmark of 27 instances derived from pre-processed elevation data. • Comparison with the best model in the literature re-implemented in this paper. • Construction of an original visualization tool for the solution output. [ABSTRACT FROM AUTHOR]

Scheduling in distributed production system has become an active research field in recent years. This paper investigates the distributed assembly blocking flow-shop scheduling problem (DABFSP), which consists of two stages: production and assembly. The first stage is processing jobs in several identical factories. Each factory has a series of machines no intermediate buffers existing between adjacent ones. The second stage assembles the processed jobs into the final products through a single machine. The objective is to minimize the maximum completion time or makespan of all products. To address this problem, a constructive heuristic is proposed based on a new assignment rule of jobs and a product-based insertion procedure. Afterwards, an iterated local search (ILS) is presented, which integrates an integrated encoding scheme, a multi-type perturbation procedure containing four kinds of perturbed operators based on problem-specific knowledge and a critical-job-based variable neighborhood search. Finally, a comprehensive computational experiment and comparisons with the closely related and well performing methods in the literature are carried out. The experimental and comparison results show that the proposed constructive heuristic and ILS can solve the DABFSP effectively and efficiently. [ABSTRACT FROM AUTHOR]

With the rapid development of make-to-order pattern including E-commerce and takeout and catering service in restaurants, the study of integrated scheduling and distribution receives more and more attentions. Based on a practical order picking and distribution system, a three-stage hybrid flow shop scheduling problem with distribution is studied. Each order is processed on the hybrid flow shop which consists of identical parallel machines with sequence-dependent setup times at stage 1, identical parallel machines at stage 2 and dedicated machines at stage 3, followed by a multi-trip traveling salesman problem with capacitated vehicles for customers of different destination areas. A mixed-integer linear programming model is formulated to minimize the maximum delivery completion time. A variable neighborhood search (VNS)-based method, a four-layered constructive heuristic method (denoted by C H VNS ) and a hybrid heuristic method (denoted by C O N S VNS ) which combines the VNS method and the C H VNS method are developed to solve the problems with practical size. Computational experiments show the effectiveness and efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

Recent systems applying Machine Learning (ML) to solve the Traveling Salesman Problem (TSP) exhibit issues when they try to scale up to real case scenarios with several hundred vertices. The use of Candidate Lists (CLs) has been brought up to cope with the issues. A CL is defined as a subset of all the edges linked to a given vertex such that it contains mainly edges that are believed to be found in the optimal tour. The initialization procedure that identifies a CL for each vertex in the TSP aids the solver by restricting the search space during solution creation. It results in a reduction of the computational burden as well, which is highly recommended when solving large TSPs. So far, ML was engaged to create CLs and values on the elements of these CLs by expressing ML preferences at solution insertion. Although promising, these systems do not restrict what the ML learns and does to create solutions, bringing with them some generalization issues. Therefore, motivated by exploratory and statistical studies of the CL behavior in multiple TSP solutions, in this work, we rethink the usage of ML by purposely employing this system just on a task that avoids well-known ML weaknesses, such as training in presence of frequent outliers and the detection of under-represented events. The task is to confirm inclusion in a solution just for edges that are most likely optimal. The CLs of the edge considered for inclusion are employed as an input of the neural network, and the ML is in charge of distinguishing when such edge is in the optimal solution from when it is not. The proposed approach enables a reasonable generalization and unveils an efficient balance between ML and optimization techniques. Our ML-Constructive heuristic is trained on small instances. Then, it is able to produce solutions—without losing quality—for large problems as well. We compare our method against classic constructive heuristics, showing that the new approach performs well for TSPLIB instances up to 1748 cities. Although ML-Constructive exhibits an expensive constant computation time due to training, we proved that the computational complexity in the worst-case scenario—for the solution construction after training—is O(n2logn2), n being the number of vertices in the TSP instance.

In this paper, we consider the time-dependent multi-depot vehicle routing problem. The objective is to minimize the total heterogeneous fleet cost assuming that the travel time between locations depends on the departure time. Also, hard time window constraints for the customers and limitation on maximum number of the vehicles in depots must be satisfied. The problem is formulated as a mixed integer programming model. A constructive heuristic procedure is proposed for the problem. Also, the efficiency of the proposed algorithm is evaluated on 180 test problems. The obtained computational results indicate that the procedure is capable to obtain a satisfying solution.

The blocking flow shop problem (BFSP) is one of the key models in the flow shop scheduling problem in the manufacturing systems. Gravitational Search Algorithm (GSA) is an algorithm based on the population for solving various optimization problems. However, GSA is scarcely applied to solve the BFSP as it is designed to solve the continuous problems. In this paper, a Discrete Gravitational Search Algorithm (DGSA) is presented for solving the BFSP with the total flow time minimization. A new variable profile fitting (VPF) combined with NEH heuristic, named VPF _ NEH(n), is introduced for balancing the quality and the diversity of the initial population to configure the DGSA. The three operators including the variable neighborhood operators (VNO), the path relinking and the plus operator are implemented during the location updating of the candidates. The objective of the operation is to prevent the premature convergence of the population and to balance the exploration and exploitation in the process of optimization. The expected runtime of the DGSA is analyzed by the level-based theorem. The simulated results indicate that the effectiveness and superiority of the DGSA. [ABSTRACT FROM AUTHOR]

Due to the complexity of a real-practice manufacturing process, various complex constraints should be considered to make the conventional model more suitable for the realistic production. This paper proposes a distributed assembly no-idle flow shop scheduling problem (DANIFSP) with the objective of minimizing the makespan at the assembly stage. The DANIFSP consists of two stages, i.e., production and assembly. The production stage contains several identical flow shops working in parallel, in which all jobs with series of operations that should be allocated to one of these factories and all operations of jobs should be performed in the allocated factories. To satisfy the no-idle constraint, each machine must process jobs without any interruption from the start of processing the job to the completion of processing the last job. In the second assembly stage, the processed jobs are assembled by a single machine. For addressing the DANIFSP, this paper extends three constructive heuristics based on a new job assignment rule and proposes two simple meta-heuristics including iterated local search (ILS) and variable neighborhood search (VNS). A comprehensive calibration and analysis for the proposed algorithms through a design of experiments are carried out. The comparison with recently published algorithms demonstrates the high effectiveness of the proposed ILS and VNS. [ABSTRACT FROM AUTHOR]

Abstract The negative appraisals of the impact of airline industry on climate change have forced the industry to become greener. Over the past several decades, CO 2 emissions in the airline industry have increased considerably, thereby adversely affecting the environment. Therefore, airlines are seeking different approaches to reduce the environmental degradation. In this paper, we study cruise speed control to achieve this goal by reducing CO 2 emissions while studying passenger service level. We use some indicators to measure the passenger service level in the airline industry. These indicators create a conflict between CO 2 emissions and passenger service level. We develop a bi-objective mixed-integer non-linear programming model to integrate flight scheduling, aircraft-path assignment, and gate assignment with the aim of reducing CO 2 emissions while increasing passenger service level. Based on a real problem, the model can lead to 11% and 31% improvement in CO 2 emissions and passenger service level, respectively. The model is NP-hard. Therefore, we develop a new constructive heuristic method, and we also use the multi-objective simulated annealing algorithm and extend this algorithm to enhance its performance. We also use the design of experiment and Taguchi method to optimize the algorithms parameters. Finally, we evaluate the proposed methods based on information retrieved from major U.S. airlines. [ABSTRACT FROM AUTHOR]

Currently, energy consumption reduction is playing a more and more important role in production and manufacturing, especially for energy-intensive industries. An optimal production scheduling can help reduce unnecessary energy consumption. This paper considers an identical parallel machine scheduling problem to minimize simultaneously two objectives: the total energy consumption (TEC) and the makespan. To tackle this NP-hard problem, an augmented ɛ -constraint method is applied to obtain an optimal Pareto front for small-scale instances. For medium- and large-scale instances, a constructive heuristic method with a local search strategy is proposed and the NSGA-II algorithm is applied to obtain good approximate Pareto fronts. Extensive computational experiments on randomly generated data and a real-world case study are conducted. The result shows the efficiency and effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]