Search

The distributed permutation flow shop scheduling problem (DPFSP) has received increasing attention in recent years. The iterated greedy algorithm (IGA) serves as a powerful optimizer for addressing such a problem because of its straightforward, single-solution evolution framework. However, a potential draw-back of IGA is the lack of utilization of historical information, which could lead to an imbalance between exploration and exploitation, especially in large-scale DPFSPs. As a consequence, this paper develops an IGA with memory and learning mechanisms (MLIGA) to efficiently solve the DPFSP targeted at the mini-mal makespan. In MLIGA, we incorporate a memory mechanism to make a more informed selection of the initial solution at each stage of the search, by extending, reconstructing, and reinforcing the information from previous solutions. In addition, we design a two-layer cooperative reinforcement learning approach to intelligently determine the key parameters of IGA and the operations of the memory mechanism. Meanwhile, to ensure that the experience generated by each perturbation operator is fully learned and to reduce the prior parameters of MLIGA, a probability curve-based acceptance criterion is proposed by combining a cube root function with custom rules. At last, a discrete adaptive learning rate is employed to enhance the stability of the memory and learning mechanisms. Complete ablation experiments are utilized to verify the effectiveness of the memory mechanism, and the results show that this mechanism is capable of improving the performance of IGA to a large extent. Furthermore, through comparative experiments involving MLIGA and five state-of-the-art algorithms on 720 benchmarks, we have discovered that MLI-GA demonstrates significant potential for solving large-scale DPFSPs. This indicates that MLIGA is well-suited for real-world distributed flow shop scheduling. [ABSTRACT FROM AUTHOR]

The customer order scheduling problem has garnered considerable attention in the recent scheduling literature. It is assumed that each of several customer orders consists of several jobs, and each customer order is completed only if each job of the order is completed. In this paper, we consider the customer order scheduling problem in a machine environment where each customer places exactly one job on each machine. The objective is to minimize the earliness–tardiness, where tardiness is defined as the time an order is finished past its due date, and earliness is the time a job is finished before its due date or the completion time of the corresponding order, whichever is later. Even though the earliness–tardiness criterion is an important objective for just-in-time production, this problem has not been studied in the context of the customer order scheduling problem. We provide a mixed-integer linear programming (MILP) formulation for this problem and derive multiple problem properties. Furthermore, we develop six different heuristics for this problem configuration. They follow the structure of the iterated greedy algorithm and additionally use a refinement function in which they differ. In a computational experiment, the algorithms were compared with each other and outperformed a solver solution of the MILP, which proves their ability to efficiently solve the problem configuration. [ABSTRACT FROM AUTHOR]

This paper focuses on the precast supply chain scheduling problem with time-dependent transportation time to minimise the total weighted tardiness (PSCSP_TDT |TWT). In the problem, an order sequence and several job sequences are to be determined simultaneously. At first, through in-depth analysis of problem structure and real data from a precast manufacturer, we approximate the problem into a three-stage order scheduling problem by combining the seven production stages into one differentiation stage, and then explore some useful properties of the schedules for the approximate problem. Subsequently, to solve the small instances for the PSCSP_TDT |TWT, we propose an approximate model-based hybrid dynamic programming and heuristic (AMHDPH) and obtain a lower bound as a by-product of the algorithm. For dealing with medium-or large instances, with considering the complexity of the problem, we propose four approximate model-based hybrid iterated greedy (AMHIG) algorithms by integration of constructive heuristics, structural properties of solutions, an iterated greedy, and a correction heuristic. Comprehensive computational results show that the AMHDPH generates tight lower bounds for small instances and solves the most of small instances to optimality within 60 seconds. Whereas the best AMHIG generates feasible solutions with an average optimality gap below 5 percent for around 70 percent instances. [ABSTRACT FROM AUTHOR]

The hybrid flow shop group scheduling problem (HFGSP) with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode. However, there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP. In our study, we place emphasis on the constraint of timeliness. Therefore, this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness (TWET). Then a penalty groups-assisted iterated greedy integrating idle time insertion (PG_IG_ITI) is proposed to solve the above problem. In the PG_IG_ITI, a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value. Subsequently, to reduce the amount of computation, a skip-based destruction and reconstruction strategy is designed, and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups, i.e., early and tardy groups. Finally, through comprehensive statistical experiments on 270 test instances, the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.

Copyright of Control Theory & Applications / Kongzhi Lilun Yu Yinyong is the property of Editorial Department of Control Theory & Applications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The distributed no-idle permutation flowshop scheduling problem has gained significant attention as a prominent area of research in recent years, particularly in industries where setup operations are so expensive that reactivating the machines is not cost-effective. This study addresses an extension of the distributed permutation flowshop scheduling problem with no-idle and due window constraints. The aim is to determine the job assignments to the factories and their sequences in each factory that provide the minimum total weighted earliness and tardiness (TWET) penalties considering due windows. This study is the first to formulate this problem, offering four different mathematical models, and presents a benchmark to examine different problem cases that may arise in practical applications. Furthermore, to effectively solve the diverse problem instances, two hybrid metaheuristic algorithms based on the Iterated Greedy are proposed. These metaheuristics exhibit promising capabilities, enabling the solution of problem instances involving up to 500 jobs. To assess the effectiveness of the proposed models and algorithms, extensive numerical experiments are conducted, facilitating a thorough evaluation and comparison of their performances. [ABSTRACT FROM AUTHOR]

This paper investigated a parallel machine scheduling problem in the printing manufacturing systems due to operational requirements on the color-batching of the printed matter and sequential requirements on the sequence adherence of a printing press. Resequencing printing jobs as color-oriented batches reduced the costs of color changes and operational costs for printing shop. Also, post press workshop required printing shops to print jobs with minimal makespan so that high sequence adherence with its demand is assured. Based on real-world applications, we investigated two contradictory objectives-color change costs and minimal makespan-in a parallel high-fidelity printing press scheduling environment. A job sequence optimization approach is proposed. Moving interpolation algorithm and color sequence mapping algorithm are designed to reduce frequency of replacing ink. Base on iterative greedy algorithm, color sequence job groups with the same or similar color sequence are scheduled to the printing presses. Three experiments are conducted and showed that the proposed approach has good feasibility and effectiveness, and convergence in solving minimum completion time. Therefore, the proposed approach can be used in printing shops to improve scheduling efficiency and reduce production costs.

The distributed hybrid flow shop scheduling problem (DHFSP), which integrates distributed manufacturing models with parallel machines, has gained significant attention. However, in actual scheduling, some adjacent machines do not have buffers between them, resulting in blocking. This paper focuses on addressing the DHFSP with blocking constraints (DBHFSP) based on the actual production conditions. To solve DBHFSP, we construct a mixed integer linear programming (MILP) model for DBHFSP and validate its correctness using the Gurobi solver. Then, an advanced iterated greedy (AIG) algorithm is designed to minimize the makespan, in which we modify the Nawaz, Enscore, and Ham (NEH) heuristic to solve blocking constraints. To balance the global and local search capabilities of AIG, two effective inter-factory neighborhood search strategies and a swap-based local search strategy are designed. Additionally, each factory is mutually independent, and the movement within one factory does not affect the others. In view of this, we specifically designed a memory-based decoding method for insertion operations to reduce the computation time of the objective. Finally, two shaking strategies are incorporated into the algorithm to mitigate premature convergence. Five advanced algorithms are used to conduct comparative experiments with AIG on 80 test instances, and experimental results illustrate that the makespan and the relative percentage increase (RPI) obtained by AIG are 1.0% and 86.1%, respectively, better than the comparative algorithms.

During recent years, the distributed permutation flowshop scheduling problem (DPFSP) has become a very active area of research. However, minimising total tardiness in DPFSP, a very essential and relevant objective for today's customer-orientated market, has not been studied much. In this paper, we address the DPFSP with the total tardiness criterion. We present a mixed-integer linear programming model, two heuristics, hybrid discrete Harris hawks optimisation and an enhanced variant of iterated greedy algorithm to solve the considered problem. Problem-specific knowledge is explored and effective technologies, such as path relinking and random sub-sequence/single-point local search, are employed to improve the presented algorithms. The operators and parameters of the algorithms are analysed and calibrated using the design of experiments. To evaluate the performance, the well-known benchmark problem set of Naderi and Ruiz for DPFSP is extended with due dates. We compare the presented algorithms against seven other well-known meta-heuristics from the literature. Statistically sound results demonstrate the effectiveness of the presented algorithms for the considered problem. [ABSTRACT FROM AUTHOR]

Yarn dyeing is a critical link in the textile production chain that consumes the most time and energy. Today's dyeing shops receive hundreds of demands with thousands of different colors, different due dates, and different production requirements. This situation has made it very difficult for the human brain to create a minimum‐cost production plan by complying with the due dates. In this study, a real‐life problem of a company operating in the textile industry is discussed and a solution has been developed for the planning of yarn‐dyeing boilers. The application was held in Bursalı Textile, which is the major towel manufacturer operating in Turkey. The problem dealt with is basically in the nature of the variable‐size bin‐packing problem (VSBPP). The limited availability of bins (boilers) of different sizes and the packing of the items (yarn work orders) with due date constraints are the original aspects of this study. Multi‐objective mixed integer programming model is developed to minimize two objectives. For the solution, the preemptive method called the lexicographic approach, in which the objectives are solved in order, is preferred. As the first objective, the overcapacity usage is minimized and then the second objective, which is the boiler usage cost, is minimized. Given that the VSBPP is strongly NP‐hard, an iterated greedy algorithm with two different decoding approaches is proposed. Computational experiments were conducted on 20 randomly generated benchmark instances and a real‐world industrial dataset. The numerical results show that good solutions can be obtained in seconds using the proposed approaches. [ABSTRACT FROM AUTHOR]

This article addresses the no-wait permutation flowshop layout where the jobs must be processed continuously in the available machines without interruption. The objective function is weighted quadratic tardiness minimization. Since the problem under study is NP-hard, an iterated greedy algorithm is introduced where the parameters are selected according to a variable neighbourhood descent framework. In the authors' innovative algorithm, in the first iteration of the search process, the parameters are initialized with a fixed number. In the remaining iterations, such parameters are reduced deterministically, aiming to explore distinct values throughout the search process. The proposal is compared with five other algorithms proposed for closely related problems, considering two performance measures: the Relative Deviation Index (RDI) and the Success Rate (SR). The proposed algorithm produced average values of RDI and SR of 1.2% and 86.9%, respectively. The computational results demonstrated that the authors' proposal outperformed all the other five algorithms under comparison. [ABSTRACT FROM AUTHOR]

This research paper addresses a novel parallel machine scheduling problem with re-entrant and group processing features, specifically motivated by the hot milling process in the modern steel manufacturing industry. The objective is to minimize the makespan. As no existing literature exists on this problem, the paper begins by analyzing the key characteristics of the problem. Subsequently, a mixed integer linear programming model is formulated. To tackle the problem, an improved iterated greedy algorithm (IGA) is proposed. The IGA incorporates a problem-specific heuristic to construct the initial solution. Additionally, it incorporates an effective destruction and reconstruction procedure. Furthermore, an acceptance rule is developed to prevent the IGA from getting stuck in local optima. The proposed approach is evaluated through computational experiments. The results demonstrate that the proposed IGA outperforms three state-of-the-art meta-heuristics, highlighting its high effectiveness. Overall, this research contributes to the understanding and solution of the parallel machine scheduling problem with re-entrant and group processing features in the context of the hot milling process. The proposed algorithm provides insights for practical applications in the steel manufacturing industry.

In recent years, both distributed scheduling and energy-efficient scheduling have attracted great attention in production systems. This paper studies an energy-efficient distributed blocking flowshop scheduling problem where several heterogeneous factories cooperate to process jobs. A knowledge-based iterated Pareto greedy algorithm (KBIPG) is proposed to minimize simultaneously the makespan and total energy consumption. Based on a speed scaling framework that allows machines to process different jobs at different speed levels or remain in the standby mode, the KBIPG has two stages, where the difference lies in whether to adjust the processing speed. First, two multi-objective insertion procedures are proposed to form construction procedures. Second, we presented an efficient destruction procedure for each stage separately. Third, two local intensification methods are designed based on adjusting machine speeds, including the energy-saving procedure that optimizes the total energy consumption and the speedup-based local search procedure that optimizes the makespan. The KBIPG algorithm starts with generating solutions under various initial machine speed matrixes with different levels and then goes through a two-stage loop based on the proposed procedures. Computational experiments and comparisons with five algorithms demonstrate the effectiveness of the proposed KBIPG algorithm. [ABSTRACT FROM AUTHOR]

As multi-factory production models are more widespread in modern manufacturing systems, a distributed blocking flowshop scheduling problem (DBFSP) is studied in which no buffer between adjacent machines and setup time constraints are considered. To address the above problem, a mixed integer linear programming (MILP) model is first constructed, and its correctness is verified. Then, an iterated greedy-algorithm-blending multi-factory collaboration mechanism (mIG) is presented to optimize the makespan criterion. In the mIG algorithm, a rapid evaluation method is designed to reduce the time complexity, and two different iterative processes are selected by a certain probability. In addition, collaborative interactions between cross-factory and inner-factory are considered to further improve the exploitation and exploration of mIG. Finally, the 270 tests showed that the average makespan and RPI values of mIG are 1.93% and 78.35% better than the five comparison algorithms on average, respectively. Therefore, mIG is more suitable to solve the studied DBFSP_SDST. [ABSTRACT FROM AUTHOR]

This work investigates an unmanned aerial vehicle (UAV) assisted IoT system, where a UAV flies to each foothold to collect data from IoT devices, and then return to its start point. For such a system, we aim to minimize the energy consumption by jointly optimizing the deployment and flight trajectory of UAV. It is a mixed-integer non-convex and NP-hard problem. In order to address it, a bilevel optimization approach is proposed, where an upper-level method aims to optimize the deployment of UAV and a lower-level one aims to plan UAV flight trajectory. Specifically, the former optimizes the number and locations of footholds of UAV. This work proposes an improved dandelion algorithm with a novel encoding strategy, in which each dandelion represents a foothold of UAV and the entire dandelion population is seen as an entire deployment. Then, two mutation strategies are designed to adjust the number and locations of footholds. Based on the footholds of the UAV provided by the former, the latter transforms flight trajectory planning into a traveling salesman problem (TSP). This work proposes an iterated greedy algorithm to solve it efficiently. The effectiveness of the proposed bilevel optimization approach is verified on ten instances, and the experimental results show that it significantly outperforms other benchmark approaches. [ABSTRACT FROM AUTHOR]

• We propose a population-based iterated greedy algorithm enhanced with Q-learning for a multi-weeding-robots operation scheduling problem. • An problem-related IBH is designed to generate a set of initial solutions and a local search based on the high-load robot and the critical robot is proposed. • An effective destruction phase is developed, based on the adaptive destruction intensity and Q-learning framework. • Experimental results demonstrate the effectiveness of the Q_DPIG based on the test datasets and a real case study from a farmland management center. With technological advancements, robots have been widely used in various fields and play a vital role in the production execution system of a smart farm. However, the operation scheduling problem of robots within production execution systems has not received much attention so far. To enable efficient management, this paper develops a multi-objective mathematical model concerning both the efficiency and economic indicators. We propose a population-based iterated greedy algorithm enhanced with Q-learning (Q_DPIG) for a multi-weeding-robots operation scheduling problem. An index-based heuristic (IBH) is designed to generate a diverse set of initial solutions, while an adaptive destruction phase, guided by the Q-learning framework, ensures effective neighborhood search and solution optimization. Additionally, a local search method focusing on the high-load and the critical robots is employed to further optimize the two objectives. Finally, Q_DPIG is demonstrated to be effective and significantly outperform the state-of-the-art algorithms through comprehensive test datasets and a real case study from a farmland management center. [ABSTRACT FROM AUTHOR]

An excellent automated guided vehicle (AGV) scheduling scheme can effectively improve the productivity of automated manufacturing factories and reduce costs, so the AGV dispatching problem (AGVDP) has become a research hotspot. This paper studies AGVDP with AGV capacity and the latest delivery time to reduce the cost of the total objective consisting of AGV cost, travel cost, and penalty cost. To this end, a mixed-integer linear programming model and a multi-restart iterated greedy (MRIG) algorithm are proposed. According to the characteristics of the problem, an improved nearest neighbor-based heuristic algorithm (INNH) is proposed to generate an initial solution. INNH includes a balanced two-factor selection strategy and a multiple-try insertion strategy. In the MRIG, the destruction stage has been improved to have an adaptive parameter. To enhance the quality of the initial solution and the depth of the evolution, two improved reference local searches are proposed. Furthermore, a multi-restart strategy with a checking mechanism and five restart methods is designed to avoid MRIG falling into the local optimum. The results of sufficient statistical experiments show that the MRIG is obviously superior to the existing algorithms when solving AGVDP. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of multi-institutional regionalization of primary health care units. The problem consists of deciding where to place new facilities, capacity expansions for existing facilities, and demand allocation in a multi-institutional system to minimize the total travel distance from demand points to health care units. It is known that traditional exact methods as branch-and-bound are limited to solving small- to medium-size instances of the problem. Given that real world-instances can be large, in this paper we propose an iterated greedy algorithm with variable neighborhood descent search for handling large-scale instances. Within this solution framework, several methods are developed. A greedy constructive method and two deconstruction strategies are developed. Another interesting component is the exact optimization of a demand allocation subproblem that is obtained when the location of facilities is previously fixed. An empirical assessment using real-world data from the State of Mexico's Public Health Care System is carried out. The results demonstrate the effectiveness of the proposed metaheuristic in handling large-scale instances. [ABSTRACT FROM AUTHOR]

Recently, problems related to structural balance have received widespread attention in the research fields of signed networks, such as signed network partition, community detection and correlation clustering. Structural balance problems aim to find a partition of a signed network such that the frustration index, the sum of positive edges between subsets and negative edges within subsets, is minimized, which is known to be nondeterministic polynomial-time (NP)-complete and remains an open challenge. Many heuristic and meta-heuristic algorithms are developed to minimize the frustration index. However, most extant algorithms require quite a few parameters and are not efficient enough for large signed networks. In this study, we present a simple and effective iterated greedy (IG) algorithm for solving the structural balance problems with the objective of frustration minimization. In the algorithm, a constructive greedy heuristic is proposed to generate and reconstruct solutions to the problem with high efficiency. A two-stage local search procedure is designed to exploit the search space at different levels of granularity. An adaptive destruction method is developed to enhance the exploitation ability of the algorithm in the early stage and maintain the exploration ability later. Additionally, two acceleration methods are proposed to help the algorithm get a better performance in large signed networks. The experimental results indicate that the proposed IG algorithm outperforms other meta-heuristics in the literature especially in terms of the computational time. [ABSTRACT FROM AUTHOR]

This paper studies the scheduling problem of jobs with release times, non-identical sizes, and incompatible job families on unrelated parallel batch machines. The capacities of batch machines and the processing times of each job on the batch machines are different. The processing time of one batch is equal to the longest processing time of jobs in this batch. Different types of jobs are not allowed to be assigned into the same batch, which is known as incompatible job families. Mixed integer linear programming and constraint programming (CP) models are proposed. A new batch-based local search method is designed and an iterated greedy (IG) algorithm is developed to avoid unreasonable exchanging of jobs during the local search. Numerical results show that the CP method can obtain high quality solutions in the small-scale instances. For the large-scale instances, the IG algorithm with the new local search method has a competitive performance. [ABSTRACT FROM AUTHOR]

Resource constrained project scheduling problems (RCPSPs) are complex optimization problems that aim to minimize project completion time after considering limited resources and precedence-related activities with known durations. However, due to the dynamic nature of real-world applications, activity durations are vulnerable to change. In addition, resource demands along with resource availability at any stage of a project can also vary due to disruptions, which compel practitioners to re-think existing scheduling methodologies. Consequently, to mitigate the conjoint effect of those uncertainties and/or disruptions, this paper proposes a real-time reactive scheduling approach. To deal with uncertain activity durations, a chance constrained based approach is followed, which is later solved by an advanced meta-heuristic based approaches called IGFBIS and IGFBID. After solving an exhaustive list of stochastic RCPSP instances, this paper proves the efficacy of the proposed approaches, which is proven to be more useful to mitigate uncertainty or disruption while executing real-life projects.

Aimed at the no-idle flow-shop scheduling problem (NIFSP) with minimized makespan, a discrete sine optimization algorithm (DSOA) is proposed. Inspired by sine waveforms, the original sine optimization algorithm (SOA) is a global optimization algorithm, which uses the sine function to update the position of search agents. First, the update position strategy to adapt to the combinatorial optimization problem is redefined. An iterated greedy algorithm with a variable removing size is employed to update the position to enhance the exploration ability. Then, a crossover strategy and a selection strategy are applied to avoid the algorithm falling into local optimum. Next, to improve the exploitation ability of local search and the accuracy of the algorithm, an insertion-based local search scheme is applied in DSOA to search for a better solution around the current optimal solution. Finally, based on the Taillard benchmark, the simulation results of performance comparisons are presented. The experimental results demonstrate the effectiveness of the proposed DSOA algorithm for solving NIFSP.

This paper proposes new block properties for the flowshop scheduling problem with blocking to minimise makespan. A pruning procedure based on these proposed properties is used in the construction phase of an iterated greedy algorithm to decrease the total number of solutions to be examined to find an optimal schedule. Computational results using Taillard’s benchmark problem instances show that the new block properties help to eliminate more ‘unpromising’ solutions than the classic properties. In addition, the effectiveness of the proposed algorithm is verified by comparison with some high-performing algorithms for the considered problem. [ABSTRACT FROM AUTHOR]

Generally, optimization is the achievement of the best result under certain constraints. Basically, the approaches developed for the solution of optimization problems are examined under two groups as exact solution methods and approximate solution methods. Exact solution methods guarantee the optimum, but they cannot produce solutions in an acceptable time for large-scale real-life problems of NP-Hard. Therefore, the researchers draw great attention to the meta-heuristic methods, which are one of the approximate solution methods, because they can provide quality solutions at an acceptable time. In this study, a detailed analysis of the iterative greedy algorithm, which is an easy-to-apply and effective meta-heuristic, was conducted. In the relevant meta-heuristic, each operator is discussed under subheadings. Iterative greedy algorithm approaches developed for various problems are presented to the reader with their advantages and disadvantages. In summary, in this study, it is aimed to contribute to the Turkish literature about the iterative greedy algorithm, which has many aspects in common with various meta-heuristics such as taboo, annealing simulation, and iterative local search. [ABSTRACT FROM AUTHOR]

Distributed manufacturing paradigm is becoming one of the dominant manufacturing models today. Heterogeneities between factories exist in fact due to the differences in process flexibility and machine performance. Most research focuses on identical distributed factories and overlooks the influence of heterogeneous factories on the subproblem of job allocation. This paper investigates a distributed heterogeneous permutation flowshop scheduling problem (DHPFSP) to minimize the makespan, and a mixed-integer linear programming (MILP) model is established. Building upon a special phenomenon of job assignment to a specific heterogeneous factory in DHPFSP, an iterated greedy algorithm with acceleration of job allocation probability (IGP) is proposed. To utilize this phenomenon, a job allocation probability matrix is introduced to describe the trend of job allocation, and a fast pass strategy with job allocation probability is suggested to speed up the algorithm search process. Furthermore, to generate a high-quality initial solution quickly for IGP, an NEH-based heuristic framework for distributed heterogeneous factory environment (NEHDHF) is proposed. In NEHDHF, several distinct initial job sequence generation strategies and a new first-f job allocation strategy are proposed for obtain a better initial solution. In computational experiments, there are 720 test instances designed and publicized. The IGP achieves 535 best solutions out of 720 instances. Statistically sound results demonstrate the effectiveness of the presented algorithms for the considered problem. [ABSTRACT FROM AUTHOR]

As the interest of practitioners and researchers in scheduling in a multi-factory environment is growing, there is an increasing need to provide efficient algorithms for this type of decision problems, characterised by simultaneously addressing the assignment of jobs to different factories/workshops and their subsequent scheduling. Here we address the so-called distributed permutation flowshop scheduling problem, in which a set of jobs has to be scheduled over a number of identical factories, each one with its machines arranged as a flowshop. Several heuristics have been designed for this problem, although there is no direct comparison among them. In this paper, we propose a new heuristic which exploits the specific structure of the problem. The computational experience carried out on a well-known testbed shows that the proposed heuristic outperforms existing state-of-the-art heuristics, being able to obtain better upper bounds for more than one quarter of the problems in the testbed. [ABSTRACT FROM PUBLISHER]

For the minimisation of total tardiness in no-wait flowshops, objective incremental properties are investigated in this paper to speed up the evaluation of candidate solutions. To explore the properties, we introduce a new concept of sensitive jobs and identify through experiments that the proportion of such jobs is very small. Instead of evaluating the tardiness of each job, we focus on the evaluation of sensitive jobs which will help to reduce the computational efforts. With these properties, the time complexity of the NEH-insertion procedure is reduced from to approximately in average. Then, an accelerated NEH algorithm and an accelerated iterated greedy algorithm are designed for the problem. Since the NEH-insertion procedure constitutes the main computational burden for both algorithms, these algorithms will benefit directly from the speedup. Numerical computations show that the accelerated algorithms perform 10–40 times faster than the original algorithms on the middle- and large-sized instances. In addition, comparisons show that the proposed algorithms perform more efficiently and effectively than the existing heuristics and meta-heuristics. [ABSTRACT FROM AUTHOR]

This study examines a two-stage three-machine flow-shop assembly scheduling model in which job processing time is considered as a mixed function of a controlled truncation parameter with a sum-of-processing-times-based learning effect. However, the truncation function is very limited in the two-stage flow-shop assembly scheduling settings. To overcome this limitation, this study investigates a two-stage three-machine flow-shop assembly problem with a truncation learning function where the makespan criterion (completion of the last job) is minimized. Given that the proposed model is NP hard, dominance rules, lemmas and a lower bound are derived and applied to the branch-and-bound method. A dynamic differential evolution algorithm, a hybrid greedy iterated algorithm and a genetic algorithm are also proposed for searching approximate solutions. Results obtained from test experiments validate the performance of all the proposed algorithms. [ABSTRACT FROM AUTHOR]

Optimization is the selection of the best possible solution (min / max) under certain criteria. For the solution of optimization problems; many approaches have been developed in different classes such as exact solution methods, approximation methods, meta-heuristic techniques. However, the enormous size of real-life problems have led researchers to meta-heuristic techniques that provide acceptable solutions in a short time. In this study, an application has been made with the iterated greedy algorithm, which stands out with its simple structure. Flexible job shop scheduling problem is addressed for application. Basically, the iterative greedy algorithm starts the optimization process with a single solution. The current solution then enters the construction-destruction phase to find a better solution. The solution obtained after this stage is replaced with the incumbent solution according to the previously determined acceptance criteria. This cycle, which consists of two operators, construction and destruction, continues until a certain stopping criterion is met. In this study, a problem-specific critical path-based approach was developed in the construction-destruction phase. In addition, a novel approach based on the acceptance of solutions of decreasing quality depending on the number of iterations is proposed. The aim of this study is to contribute to the limited Turkish literature on the application of meta-heuristic algorithms in various fields. [ABSTRACT FROM AUTHOR]

This study focuses on streamlining the order-picking process in a warehouse. We consider determining the picking sequence of items in a pick-list to minimize the total traveled distance in a multiblock warehouse, where a low-level picker-to-parts manual picking system is employed. We assume that the items are stored randomly in the warehouse. First, we construct a distance matrix of the shortest path between any pair of items. Next, using the distance matrix, we implement two meta-heuristics--the tabu search algorithm and the iterated greedy algorithm--to determine the picking sequence with the minimum total traveled distance. Through a numerical study, the performances of the meta-heuristic algorithms are compared with those of popular rule-based heuristics (S-shape, largest gap, and Combined+) and the bestknown solutions. We conducted the numerical study in two stages. In the first stage, we considered a two-block rectangular warehouse, and in the second stage, we considered a three-block rectangular warehouse. The performance of the heuristics was calculated based on the optimal solution when available or the best calculated bound when the optimal solution is not available. We observed that the iterated greedy algorithm significantly outperforms the other heuristics for both stages. [ABSTRACT FROM AUTHOR]

Community structure is one of the most important properties in complex networks. Detecting such communities plays an important role in a wide range of applications such as information sharing and diffusion, recommendation, and classification. In this paper, we propose a novel iterated greedy algorithm for detecting communities in complex networks. The algorithm is based on an iterative process that combines a destruction phase and a reconstruction phase. During the destruction phase, the algorithm destructs community indexes of a certain percent nodes having lower modularity contribution. In the reconstruction phase, their community indexes are reconstructed using the well-known Louvain construction heuristic. A local search procedure can be applied after the reconstruction phase to improve the performance of the algorithm. Experiments on the computer-generated networks and real-world networks show that our algorithm is very efficient and competitive compared with several state-of-the-art methods. [ABSTRACT FROM AUTHOR]

In this paper, a problem arising in the planning of specialized diagnostic services in a segmented public healthcare system is addressed. The problem consists of deciding which hospitals will provide the service and their capacity levels, the allocation of demand in each institution, and the reallocation of uncovered demand to other institutions or private providers, while minimizing the total equivalent annual cost of investment and operating cost required to satisfy all the demand. An associated mixed-integer linear programming model can be solved by conventional branch and bound for relatively small instances; however, for larger instances the problem becomes intractable. To effectively address larger instances, a hybrid metaheuristic framework combining iterated greedy (IGA) and variable neighborhood descent (VND) components for this problem is proposed. Two greedy construction heuristics are developed, one starting with an infeasible solution and iteratively adding capacity and the other starting with a feasible, but expensive, solution and iteratively decrease capacity. The iterated greedy algorithm includes destruction and reconstruction procedures. Four different neighborhood structures are designed and tested within a VND procedure. In addition, the computation of local search components benefit from an intelligent exploitation of problem structure since, when the first-level location variables (hospital location and capacity) are fixed, the remaining subproblem can be solved efficiently as it is very close to a transshipment problem. All components and different strategies were empirically assessed both individually and within the IGA-VND framework. The resulting metaheuristic is able to obtain near optimal solutions, within 3% of optimality, when tested over a data base of 60- to 300-hospital instances. [ABSTRACT FROM AUTHOR]

With the development of economic globalization, distributed hybrid flow shop scheduling problem (DHFSSP) has become prevalent in realistic manufacturing systems. Moreover, to accord with the actual production scenarios and satisfy the requirement of manufacturing market, it is imperative to comprehensively explore various complex manufacturing scenarios (e.g., production assembly) and production-constrained resources (e.g., worker resources) in DHFSSP. However, the integration mode of DHFSSP, assembly shop problem (ASP), and dual-resource constraints (DRC) has not been reported in existing literature. Thus, to fill out this research gap, this paper first attempts to investigate DAHFSSP-DRC with minimization the total tardiness (T T D). To solve this problem, a mixed-integer linear programming (MILP) model and a knowledge-based iterated greedy algorithm (KBIG) are presented. The novelties of KBIG are as follows: (1) An efficient decoding is developed to improve the solution's quality; (2) A knowledge-based NEH (KB-NEH) initialization strategy is presented to generate an initial solution; (3) A knowledge-based destruction and construction is designed to improve the exploration capability; (4) A product-based local search is proposed to enhance the exploitation capability. Additionally, to validate the proposed model, we implement CPLEX to solve it on 24 small-sized instances. To verify the effectiveness of the proposed KBIG, extensive experiments are conducted to compare with other 7 comparison algorithms on 405 large-sized instances. Experimental results illustrate that KBIG is superior to its competitors. • This paper first investigates DAHFSSP-DRC with minimization TTD. • A MILP model and a KBIG are proposed for DAHFSSP-DRC. • The importance level of different knowledge is considered in KBIG. • Experimental results prove the effectiveness of MILP model and KBIG. [ABSTRACT FROM AUTHOR]

Distributed scheduling problems have been extensively studied due to their critical roles in industrial applications. Most research focuses on identical distributed factories and the objective of minimizing the makespan, ignoring the widely existing heterogeneous factories and delivery targets in reality. This paper aims to establish a distributed heterogeneous flowshop scheduling scenario with the objective of minimizing total tardiness (DHPFSP-t), and solve it using an improved iterative greedy algorithm. A mixed-integer programming model and several problem-specific properties are proposed for this novel scheduling scenario. Based on the distributed heterogeneous characteristics of the problem, four constructive algorithms are established to quickly generate initial solutions. Among them, the better solution is selected as the initial solution of the iterative greedy algorithm. To enhance the performance of the iterative greedy algorithm, the concept of tabu memory is incorporated and novel destruction and local search processes are devised. Thorough experiments are conducted to verify the effectiveness of the mixed-integer programming model of the scenario, the constructive heuristics and the improved iterative greedy algorithm. The result confirms the validity of the proposed model and the good performance of the proposed method. • We study a distributed heterogeneous scheduling with total tardiness criterion. • Several problem-specific properties are proposed. • We present a tabu memory based iterated greedy algorithm. • We provide a benchmark and the best obtained solutions for the problem. [ABSTRACT FROM AUTHOR]

In this paper, we studied the distributed assembly permutation flowshop scheduling problem (DAPFSP) with the makespan minimization as objective. We proposed iterated greedy-based approach that is labelled the bounded-search iterated greedy algorithm BSIG. In addition, four local search methods are designed to improve solution quality. The computational results show the effectiveness of BSIG in solving the DAPFSP specially with small instances where BSIG outperforms most of the existing algorithms. [ABSTRACT FROM AUTHOR]

In this study, we propose an improved iterated greedy algorithm for solving the distributed permutation flowshop problem, where there is a single robot in each factory and the makespan needs to be minimized. In the problem considered, the robot is used to transfer each job from the predecessor machine to the successor machine. A blocking constraint between machines is considered, thus jobs should remain on the completed machine while waiting for the robot. The loading and unloading times are considered and different for all of the jobs conducted by the robot, and the deteriorating time is also considered. In the proposed algorithm, first, four types of neighborhood structures are developed. Then, the simulated annealing algorithm is embedded in the proposed algorithm to enhance the exploration abilities. Furthermore, a problem-specific destruction and construction strategies are investigated. Finally, several realistic instances were generated to test the proposed algorithm, and its competitive performance was verified based on detailed experimental comparisons. [ABSTRACT FROM AUTHOR]

Abstract Given a vertex-weighted graph G = (V , E) and a positive integer k ≥ 2, the minimum weight vertex cover P k (MWVCP k) problem is to find a vertex subset F ⊆ V with minimum total weight such that every path of order k in G contains at least one vertex in F. For any integer k ≥ 2, the MWVCP k problem for general graphs is NP-hard. In this paper, we restrict our attention to the MWVCP 3 problem and present a multi-start iterated greedy algorithm to solve the MWVCP 3 problem. The experiments are carried out on randomly generated instances with up to 1000 vertices and 250000 edges. Our work is the first one to adopt heuristic algorithms to solve the MWVCP 3 problem, and the experimental results show that our algorithm performs reasonably well in practice. [ABSTRACT FROM AUTHOR]

The distributed flow shop group scheduling problem (DFGSP) has wide industrial applications. Due to the strong coupling of DFGSP, three issues should be solved, such as assigning groups to factories, arranging the sequence of groups in each factory and scheduling the sequence of jobs in each group. Meanwhile, the calculation for the objective has a high time complexity. To solve the above problems, we first build a mixed-integer linear programming model of DFGSP and verify its correctness by using the Gurobi solver. By exploring the implicit characteristics of the problem, two rapid evaluation methods based on group insertion and job insertion are designed to accelerate the evaluation of the objective. Then, an effective two-stage iterated greedy algorithm (tIGA) is proposed to solve the above three coupled subproblem. In the proposed tIGA, two intra-factory and inter-factory cooperative neighborhood search strategies and two intra-group and inter-group enhanced search strategies are proposed, respectively, to improve the search breadth and depth. The results of comprehensive statistical experiments on 810 test instances show that the proposed algorithm significantly outperforms the compared ones in terms of objective values and relative percentage increase values, and demonstrates the effectiveness of the proposed tIGA. • A mixed-integer linear programming (MILP) model of DFGSP is proposed. • Two rapid evaluations are designed to accelerate the calculation of the objective. • A two-stage iterated greedy algorithm is designed for solving DFGSP. • The cross-factory and inner-factory cooperative strategies are proposed. [ABSTRACT FROM AUTHOR]

Distributed permutation flowshop scheduling problems (DPFSP) have become research hotspots. However, a DPFSP with tardiness and rejection costs (DPTR), which has important practical significance, has not yet been addressed. As manufacturers are most concerned about the maximization of the total profit, this study addresses the DPFSP to maximize the total profit. A mixed-integer linear programming model is used to describe the DPTR. An iterated greedy algorithm named IG_TR is proposed. IG_TR generates initial solutions using an improved NEH heuristic using four rules based on the deadline, due date, tardiness and rejection costs. For IG_TR, a dynamic number of jobs are removed from factories in the destruction phase. In the reconstruction phase, the removed jobs and those waiting to be processed are selected to be inserted into appropriate positions in the factories. Two local search methods are designed to improve the quality of solutions generated in the reconstruction phase. During the acceptance phase, a restart mechanism is proposed to avoid falling into local optimal. The experimental results of the component analysis demonstrate the effectiveness of IG_TR. Several comprehensive experiments show that IG_TR outperforms five related algorithms. [ABSTRACT FROM AUTHOR]