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]

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]

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]

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]

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]

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]

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]

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, a discrete Water Wave Optimization algorithm (DWWO) is proposed to solve the no-wait flowshop scheduling problem (NWFSP) with respect to the makespan criterion. Inspired by the shallow water wave theory, the original Water Wave Optimization (WWO) is constructed for global optimization problems with propagation, refraction and breaking operators. The operators to adapt to the combinatorial optimization problems are redefined. A dynamic iterated greedy algorithm with a changing removing size is employed as the propagation operator to enhance the exploration ability. In refraction operator, a crossover strategy is employed by DWWO to avoid the algorithm falling into local optima. To improve the exploitation ability of local search, an insertion-based local search scheme which is utilized as breaking operator, is applied to search for a better solution around the current optimal solution. A ruling out inferior solution operator is also introduced to improve the convergence speed. The global convergence performance of the DWWO is analyzed with the Markov model. In addition, the computational results based on well-known benchmarks and statistical performance comparisons are presented. Experimental results demonstrate the effectiveness and efficiency of the proposed DWWO algorithm for solving NWFSP. [ABSTRACT FROM AUTHOR]

The distributed production lines widely exist in modern supply chains and manufacturing systems. This paper aims to address the distributed no-wait flow shop scheduling problem (DNWFSP) with the makespan criterion by using proposed iterated greedy (IG) algorithms. Firstly, several speed-up methods based on the problem properties of DNWFSP are investigated to reduce the evaluation time of neighborhood with O (1) complexity. Secondly, an improved NEH heuristic is proposed to generate a promising initial solution, where the iteration step of the insertion step of NEH is applied to the factory after inserting a new job. Thirdly, four neighborhood structures (i.e. Critical_swap_single, Critical_insert_single, Critical_swap_multi, Critical_insert_multi ) based on factory assignment and job sequence adjustment are employed to escape from local optima. Fourthly, four local search methods based on neighborhood moves are proposed to enhance local searching ability, which contains LS_insert_critical_factory 1, LS_insert_critical_factory 2, LS_swap , and LS_insert . Finally, to organize neighborhood moves and local search methods efficiently, we incorporate them into the framework of variable neighborhood search (VNS), variable neighborhood descent (VND) and random neighborhood structure (RNS). Furthermore, three variants of IG algorithms are presented based on the designed VNS, VND and RNS. The parameters of the proposed IG algorithms are tuned through a design of experiments on randomly generated benchmark instances. The effectiveness of the initialize phase and local search methods is shown by numerical comparison, and the comparisons with the recently published algorithms demonstrate the high effectiveness and searching ability of the proposed IG algorithms for solving the DNWFSP. Ultimately, the best solutions of 720 instances from the well-known benchmark set of Naderi and Ruiz for the DNWFSP are proposed. [ABSTRACT FROM AUTHOR]

• A multi-AGVs scheduling problem with charging and maintenance is studied. • A mixed-integer linear programming model with the total cost is built. • A self-adaptive iterated greedy algorithm is proposed to solve the problem. • Experimental results show the effectiveness of the proposed algorithm. The automatic guided vehicle (AGV) scheduling problem in matrix manufacturing workshop has been a research hotspot in recent years because of its wide industrial applications. However, the research on multi-AGVs scheduling problem with charging and maintenance (MAGVS CM) is rarely reported. In the paper, the MAGVS CM is investigated to reduce the total cost composed of travel cost, penalty cost and vehicle cost. To this end, a mixed-integer linear programming model and a self-adaptive iterated greedy (SAIG) algorithm are proposed. Based on the problem characteristics, a new solution presentation and the solution accelerated evaluation method are presented and applied in the SAIG. In the SAIG, several nearest-neighbor-based improved heuristics are proposed and used to generate an initial solution. A destruction procedure with self-adaptive strategy is developed to enhance the exploration capability of the algorithm. A merging local search method is used to reduce the number of AGVs as much as possible without lowering the total cost. An acceptance criterion with restart strategy is designed to determine the current solution in the next iteration. A large number of experimental results show that the proposed algorithm significantly outperforms the existing algorithms in solving the problem under consideration. [ABSTRACT FROM AUTHOR]

This paper proposes a Tabu-mechanism improved iterated greedy (TMIIG) algorithm to solve the no-wait flowshop scheduling problem with a makespan criterion. The idea of seeking further improvement in the iterated greedy (IG) algorithm framework is based on the observation that the construction phase of the original IG algorithm may not achieve good performance in escaping from local minima when incorporating the insertion neighborhood search. To overcome this limitation, we have modified the IG algorithm by utilizing a Tabu-based reconstruction strategy to enhance its exploration ability. A powerful neighborhood search method that involves insert, swap, and double-insert moves is then applied to obtain better solutions from the reconstructed solution in the previous step. Empirical results on several benchmark problem instances and those generated randomly confirm the advantages of utilizing the new reconstruction scheme. In addition, our results also show that the proposed TMIIG algorithm is relatively more effective in minimizing the makespan than other existing well-performing heuristic algorithms. [ABSTRACT FROM AUTHOR]

Due to its practicality, hybrid flowshop scheduling problem (HFSP) with productivity objective has been extensively explored. However, studies on HFSP considering green objective in distributed production environment are quite limited. Moreover, the current manufacturing mode is gradually evolving toward distributed co-production mode. Thus, this paper investigated a distributed hybrid flowshop scheduling problem (DHFSP) with objectives of minimization the makespan and total energy consumption (T E C). To address this problem, this paper designed a Pareto-based multi-objective hybrid iterated greedy algorithm (MOHIG) by integrating the merits of genetic operator and iterated greedy heuristic. In this MOHIG, firstly, one cooperative initialization strategy is proposed to boost initial solutions' quality based on the previous experience and rules. Secondly, one knowledge-based multi-objective local search method is invented to enhance the exploitation capability according to characteristics of problem. Thirdly, an energy-saving technique is developed to decrease the idle energy consumption of machine tools. Furthermore, the effectiveness of each improvement component of MOHIG is assessed by three common indicators. Finally, the proposed MOHIG algorithm is compared with other multi-objective optimization algorithms, including SPEA2, MOEA/D, and NSGAII. Experimental results indicate that the proposed MOHIG outperforms its compared algorithms in solving this problem. In addition, this research can better guide practical production in some certain environments. • Considering green scheduling in distributed hybrid flowshop environment. • Designing a new energy-saving strategy into this problem. • Proposing a Pareto-based multi-objective hybrid iterated greedy algorithm (MOHIG). • Evaluating performance of the proposed MOHIG by conducting comparison experiments. [ABSTRACT FROM AUTHOR]

An improved iterated greedy algorithm (IIGA) is proposed in this paper to solve the no-wait flow shop scheduling problem with the objective to minimize the makespan. In the proposed IIGA, firstly, a speed-up method for the insert neighborhood is developed to evaluate the whole insert neighborhood of a single solution with ( n − 1)2 neighbors in time O( n 2), where n is the number of jobs; secondly, an improved Nawaz-Enscore-Ham (NEH) heuristic is presented for constructing solutions in the initial stage and searching process; thirdly, a simple local search algorithm based on the speed-up method is incorporated into the iterated greedy algorithm to perform exploitation. The computational results based on some well-known benchmarks show that the proposed IIGA can obtain results better than those from some existing approaches in the literature. [ABSTRACT FROM AUTHOR]

Distributed Permutation Flowshop Scheduling Problem (DPFSP) has become a hot issue in recent years. However, DPFSP with uncertain processing times (DPFSP_UPT) has not been addressed so far although real manufacturing systems often encounter various uncertain factors which make processing times uncertain. In this paper, two local-search based metaheuristics, i.e., an Iterated Greedy algorithm (sIG) and an Iterated Local Search algorithm (sILS), are presented to solve the DPFSP_UPT with makespan criterion. A robust model of expect-risk rule is used to describe the DPFSP_UPT. A valid heuristic based on the well-known NEH heuristic is proposed to initialize sIG and sILS. An acceleration algorithm is adapted to save computational efforts. A destruction procedure with dynamic sizes is presented to enhance the exploration capability for sIG. A feature with the characteristic that small changes in the solution can preserve the properties of good solutions in the iterative process is applied by sILS. Both sIG and sILS use multiple local search methods to produce promising solutions by exploiting diverse search areas. Extensive experiments show that the proposed sIG and sILS perform significantly better than the five competing algorithms adapted in the literature, but there is no significant difference between sIG and sILS and each has its own advantages for different instances. • First study of the robust distributed permutation flowshop scheduling. • A MILP model is built to formulate this new problem. • A novel Iterated Greedy and a novel Iterated Local Search are proposed. • Destruction with dynamic sizes is provided to yield more diverse search areas. • Extensive experiments show the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

• We study a distributed flowshop problem with preventive maintenance. • We present a novel multi-start iterated greedy algorithm. • An improved NEH with dropout is proposed to generate searching starting-point. • A destruction with the tournament selection is well designed. • The effective of the iterated greedy is proved by extensive experiments. In recent years, distributed scheduling problems have been well studied for their close connection with multi-factory production networks. However, the maintenance operations that are commonly carried out on a system to restore it to a specific state are seldom taken into consideration. In this paper, we study a distributed permutation flowshop scheduling problem with preventive maintenance operation (PM/DPFSP). A multi-start iterated greedy (MSIG) algorithm is proposed to minimize the makespan. An improved heuristic is presented for the initialization and re-initialization by adding a dropout operation to NEH2 to generate solutions with a high level of quality and disperstiveness. A destruction phase with the tournament selection and a construction phase with an enhanced strategy are introduced to avoid local optima. A local search based on three effective operators is integrated into the MSIG to reinforce local neighborhood solution exploitation. In addition, a restart strategy is adpoted if a solution has not been improved in a certain number of consecutive iterations. We conducted extensive experiments to test the performance of the presented MSIG. The computational results indicate that the presented MSIG has many promising advantages in solving the PM/DPFSP under consideration. [ABSTRACT FROM AUTHOR]

In this paper, we propose a variable block insertion heuristic (VBIH) algorithm to solve the permutation flow shop scheduling problem (PFSP). The VBIH algorithm removes a block of jobs from the current solution. It applies an insertion local search to the partial solution. Then, it inserts the block into all possible positions in the partial solution sequentially. It chooses the best one amongst those solutions from block insertion moves. Finally, again an insertion local search is applied to the complete solution. If the new solution obtained is better than the current solution, it replaces the current solution with the new one. As long as it improves, it retains the same block size. Otherwise, the block size is incremented by one and a simulated annealing-based acceptance criterion is employed to accept the new solution in order to escape from local minima. This process is repeated until the block size reaches its maximum size. To verify the computational results, mixed integer programming (MIP) and constraint programming (CP) models are developed and solved using very recent small VRF benchmark suite. Optimal solutions are found for 108 out of 240 instances. Extensive computational results on the VRF large benchmark suite show that the proposed algorithm outperforms two variants of the iterated greedy algorithm. 236 out of 240 instances of large VRF benchmark suite are further improved for the first time in this paper. Ultimately, we run Taillard's benchmark suite and compare the algorithms. In addition to the above, three instances of Taillard's benchmark suite are also further improved for the first time in this paper since 1993. [ABSTRACT FROM AUTHOR]