An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem

In this article, an effective hybrid immune algorithm (HIA) is presented to solve the distributed permutation flow-shop scheduling problem (DPFSP). First, a decoding method is proposed to transfer a job permutation sequence to a feasible schedule considering both factory dispatching and job sequencing. Secondly, a local search with four search operators is presented based on the characteristics of the problem. Thirdly, a special crossover operator is designed for the DPFSP, and mutation and vaccination operators are also applied within the framework of the HIA to perform an immune search. The influence of parameter setting on the HIA is investigated based on the Taguchi method of design of experiment. Extensive numerical testing results based on 420 small-sized instances and 720 large-sized instances are provided. The effectiveness of the HIA is demonstrated by comparison with some existing heuristic algorithms and the variable neighbourhood descent methods. New best known solutions are obtained by the HIA for 17 out of 420 small-sized instances and 585 out of 720 large-sized instances.     

A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem

This article addresses the distributed two-stage assembly flow-shop scheduling problem (DTSAFSP) with makespan minimisation criterion. A mixed integer linear programming model is presented, and a competitive memetic algorithm (CMA) is proposed. When designing the CMA, a simple encoding scheme is proposed to represent the factory assignment and the job processing sequence; and a ring-based neighbourhood structure is designed for competition and information sharing. Moreover, some knowledge-based local search operators are developed to enhance the exploitation ability. The influence of parameter setting on the CMA is investigated using the analysis of variance method. Extensive computational tests and comparisons are carried out, which demonstrate the effectiveness of the proposed CMA in solving the DTSAFSP.     

A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking

A flow-shop scheduling problem with blocking has important applications in a variety of industrial systems but is underrepresented in the research literature. In this study, a novel discrete artificial bee colony (ABC) algorithm is presented to solve the above scheduling problem with a makespan criterion by incorporating the ABC with differential evolution (DE). The proposed algorithm (DE-ABC) contains three key operators. One is related to the employed bee operator (i.e. adopting mutation and crossover operators of discrete DE to generate solutions with good quality); the second is concerned with the onlooker bee operator, which modifies the selected solutions using insert or swap operators based on the self-adaptive strategy; and the last is for the local search, that is, the insert-neighbourhood-based local search with a small probability is adopted to improve the algorithm's capability in exploitation. The performance of the proposed DE-ABC algorithm is empirically evaluated by applying it to well-known benchmark problems. The experimental results show that the proposed algorithm is superior to the compared algorithms in minimizing the makespan criterion.     

A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks

The multistage hybrid flow-shop scheduling problem with multiprocessor tasks has been found in many practical situations. Due to the essential complexity of the problem, many researchers started to apply metaheuristics to solve the problem. In this paper, we address the problem by using particle swarm optimization (PSO), a novel metaheuristic inspired by the flocking behaviour of birds. The proposed PSO algorithm has several features, such as a new encoding scheme, an implementation of the best velocity equation and neighbourhood topology among several different variants, and an effective incorporation of local search. To verify the PSO algorithm, computational experiments are conducted to make a comparison with two existing genetic algorithms (GAs) and an ant colony system (ACS) algorithm based on the same benchmark problems. The results show that the proposed PSO algorithm outperforms all the existing algorithms for the considered problem.     

An effective shuffled frog-leaping algorithm for solving the hybrid flow-shop scheduling problem with identical parallel machines

In this article, an effective shuffled frog-leaping algorithm (SFLA) is proposed to solve the hybrid flow-shop scheduling problem with identical parallel machines (HFSP-IPM). First, some novel heuristic decoding rules for both job order decision and machine assignment are proposed. Then, three hybrid decoding schemes are designed to decode job order sequences to schedules. A special bi-level crossover and multiple local search operators are incorporated in the searching framework of the SFLA to enrich the memetic searching behaviour and to balance the exploration and exploitation capabilities. Meanwhile, some theoretical analysis for the local search operators is provided for guiding the local search. The parameter setting of the algorithm is also investigated based on the Taguchi method of design of experiments. Finally, numerical testing based on well-known benchmarks and comparisons with some existing algorithms are carried out to demonstrate the effectiveness of the proposed algorithm.     

An extended continuous estimation of distribution algorithm for solving the permutation flow-shop scheduling problem

This article proposes an extended continuous estimation of distribution algorithm (ECEDA) to solve the permutation flow-shop scheduling problem (PFSP). In ECEDA, to make a continuous estimation of distribution algorithm (EDA) suitable for the PFSP, the largest order value rule is applied to convert continuous vectors to discrete job permutations. A probabilistic model based on a mixed Gaussian and Cauchy distribution is built to maintain the exploration ability of the EDA. Two effective local search methods, i.e. revolver-based variable neighbourhood search and Hénon chaotic-based local search, are designed and incorporated into the EDA to enhance the local exploitation. The parameters of the proposed ECEDA are calibrated by means of a design of experiments approach. Simulation results and comparisons based on some benchmark instances show the efficiency of the proposed algorithm for solving the PFSP.     

An improved water wave optimization algorithm with the single wave mechanism for the no-wait flow-shop scheduling problem

In this article, a water wave optimization algorithm with a single wave mechanism, called single water wave optimization (SWWO), is proposed to solve the no-wait flow-shop scheduling problem (NWFSP) with the objective of minimizing the makespan. In the proposed SWWO, an improved Nawaz–Enscore–Ham (NEH) heuristic is applied to construct a high-quality initial candidate. In the propagation operation, a self-adaptive block-shift operation is employed. In the breaking operation, a variable neighbourhood search operation is utilized to explore the local optimal solution. According to the schema theory as presented in genetic algorithms, a crossover operation is adopted as the refraction operation. Finally, the computational results based on several benchmarks and statistical performance comparisons are presented. The experimental results demonstrate the effectiveness and efficiency of the proposed SWWO for solving the NWFSP.     

No-wait scheduling of a two-machine flow-shop to minimise the makespan under non-availability constraints and different release dates

In this paper, we consider the two-machine no-wait flow-shop scheduling problem, when every machine is subject to one non-availability constraint and jobs have different release dates. The non-availability intervals of the machines overlap and they are known in advance. We aim to find a non-resumable schedule that minimises the makespan. We propose several lower bounds and upper bounds. These bounding procedures are used in a branch-and-bound algorithm. Computational experiments are carried out on a large set of instances and the obtained results show the effectiveness of our method.     

Joint optimization of a flow-shop group scheduling with sequence dependent set-up times and skilled workforce assignment

Flow-shop sequence-dependent group scheduling (FSDGS) problem has been extensively investigated in the literature also due to many manufacturers who implemented the concept of group technology to reduce set-up costs, lead times, work-in-process inventory costs, and material handling costs. On the other hand, skilled workforce assignment (SWA) to machines of a given shop floor may represent a key issue for enhancing the performance of a manufacturing system. As the body of literature addressing the group scheduling problems ignored up to now the effect of human factor on the performance of serial manufacturing systems, the present paper moves in that direction. In particular, an M-machine flow-shop group scheduling problem with sequence-dependent set-up times integrated with the worker allocation issue has been studied with reference to the makespan minimization objective. First, a Mixed Integer Linear Programming model of the proposed problem is reported. Then, a well-known benchmark arisen from the literature is adopted to carry out an extensive comparison campaign among three properly developed metaheuristics based on a genetic algorithm framework. Once the best procedure among those tested is selected, it is compared with an effective optimization procedure recently proposed in the field of FSDGS problems, being this latter properly adapted to run the SWA issue. Finally, a further analysis dealing with the trade-off between manpower cost and makespan improvement is proposed.     

Hybrid genetic algorithm for test bed scheduling problems

In this paper, we address the scheduling problem for a heavy industry company which provides ship engines for shipbuilding companies. Before being delivered to customers, ship engines are assembled, tested and disassembled on the test beds. Because of limited test bed facilities, it is impossible for the ship engine company to satisfy all customers’ orders. Therefore, they must select the orders that can be feasibly scheduled to maximise profit. An integer programming model is developed for order selection and test bed scheduling but it cannot handle large problems in a reasonable amount of time. Consequently, a hybrid genetic algorithm (GA) is suggested to solve the developed model. Several experiments have been carried out to demonstrate the performance of the proposed hybrid GA in scheduling test beds. The results show that the hybrid GA performs with an outstanding run-time and small errors in comparison with the integer programming model.     

A two-stage AIS approach for grid scheduling problems

Grid workflow scheduling problem has been a research focus in grid computing in recent years. Various deterministic or meta-heuristic scheduling approaches have been proposed to solve this NP-complete problem. A perusal of published papers on the artificial immune system (AIS) reveals that most researchers use the clonal selection of B cells during the evolving processes and the affinity function of B cells to solve various optimisation problems. This research takes a different approach to the subject – firstly by applying a modified algorithm (Hu, T.C., 1961. Parallel sequencing and assembly line problem. Operations Research, 9 (6), 841–848) to sequence the job and this sequence is applied for further application. Secondly, the derived sequence is then used for machine allocations using the AIS approach. The proposed AIS apply B cells to reduce the antigens and then combining T helper cells and T suppressor cells to solve the grid scheduling problems. Our proposed methodology differs from other earlier approaches as follows: 1. A two-stage approach is applied using a fixed sequence derived from heuristic to allocate machine. 2. AIS apply B cells as bases and then T cells are employed next. T helper cells are used to help improve the solution and then T suppressor cells are generated to increase the diversity of the population. A new formula is proposed to calculate the affinity of the antibody with the antigen. The total difference of completion time of each job is applied instead of the difference of makespan of the schedule. This new AIS method can supplement the flaw of genetic algorithms (GA) using fitness as the basis and a new lifespan which will keep good diversified chromosomes within the population to extend the searching spaces. The experimental tests show that this novel AIS method is very effective when compared with other meta-heuristics such as GA, simulated annealing (SA), and ant colony optimisation (ACO).     

A discrete artificial bee colony algorithm for single machine scheduling problems

This paper presents a discrete artificial bee colony algorithm for a single machine earliness–tardiness scheduling problem. The objective of single machine earliness–tardiness scheduling problems is to find a job sequence that minimises the total sum of earliness–tardiness penalties. Artificial bee colony (ABC) algorithm is a swarm-based meta-heuristic, which mimics the foraging behaviour of honey bee swarms. In this study, several modifications to the original ABC algorithm are proposed for adapting the algorithm to efficiently solve combinatorial optimisation problems like single machine scheduling. In proposed study, instead of using a single search operator to generate neighbour solutions, random selection from an operator pool is employed. Moreover, novel crossover operators are presented and employed with several parent sets with different characteristics to enhance both exploration and exploitation behaviour of the proposed algorithm. The performance of the presented meta-heuristic is evaluated on several benchmark problems in detail and compared with the state-of-the-art algorithms. Computational results indicate that the algorithm can produce better solutions in terms of solution quality, robustness and computational time when compared to other algorithms.     

A hybrid water flow algorithm for multi-objective flexible flow shop scheduling problems

In this article, the multi-objective flexible flow shop scheduling problem with limited intermediate buffers is addressed. The objectives considered in this problem consist of minimizing the completion time of jobs and minimizing the total tardiness time of jobs. A hybrid water flow algorithm for solving this problem is proposed. Landscape analysis is performed to determine the weights of objective functions, which guide the exploration of feasible regions and movement towards the optimal Pareto solution set. Local and global neighbourhood structures are integrated in the erosion process of the algorithm, while evaporation and precipitation processes are included to enhance the solution exploitation capability of the algorithm in unexplored neighbouring regions. An improvement process is used to reinforce the final Pareto solution set obtained. The performance of the proposed algorithm is tested with benchmark and randomly generated instances. The computational results and comparisons demonstrate the effectiveness and efficiency of the proposed algorithm.     

Estimation of distribution algorithm with path relinking for the blocking flow-shop scheduling problem

This article presents an effective estimation of distribution algorithm, named P-EDA, to solve the blocking flow-shop scheduling problem (BFSP) with the makespan criterion. In the P-EDA, a Nawaz–Enscore–Ham (NEH)-based heuristic and the random method are combined to generate the initial population. Based on several superior individuals provided by a modified linear rank selection, a probabilistic model is constructed to describe the probabilistic distribution of the promising solution space. The path relinking technique is incorporated into EDA to avoid blindness of the search and improve the convergence property. A modified referenced local search is designed to enhance the local exploitation. Moreover, a diversity-maintaining scheme is introduced into EDA to avoid deterioration of the population. Finally, the parameters of the proposed P-EDA are calibrated using a design of experiments approach. Simulation results and comparisons with some well-performing algorithms demonstrate the effectiveness of the P-EDA for solving BFSP.     

A genetic algorithm approach for production scheduling with mould maintenance consideration

The traditional approach for maintenance scheduling concerns single-resource (machine) maintenance during production which may not be sufficient to improve production system reliability as a whole. Besides, in the literature many researchers schedule maintenance activities periodically with fixed maintenance duration. However, in a real manufacturing system maintenance activities can be executed earlier and the maintenance duration will become shorter since less time and effort are required. A practical example is that in a plastic production system, the proportion of machine-related downtime is even lower than mould-related downtime. The planned production operations are usually interrupted seriously because of the mismatch among the maintenance periods between injection machine and mould. In this connection, this paper proposes to jointly schedule production and maintenance tasks of multi-resources in order to improve production system reliability by reducing the mismatch among various processes. To integrate machine and mould maintenance tasks in production, this paper attempts to model the production scheduling with mould scheduling (PS-MS) problem with time-dependent deteriorating maintenance schemes. The objective of this paper is to propose a genetic algorithm approach to schedule maintenance tasks jointly with production jobs for the PS-MS problem, so as to minimise the makespan of production jobs.     

A hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search for job shop scheduling problems

Job shop scheduling problem (JSSP) is a typical NP-hard problem. In order to improve the solving efficiency for JSSP, a hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search is proposed in this paper, which combines the merits of Estimation of distribution algorithm and Differential evolution (DE). Meanwhile, to strengthen the searching ability of the proposed algorithm, a chaotic strategy is introduced to update the parameters of DE. Two mutation operators are adopted. A neighbourhood search (NS) algorithm based on blocks on critical path is used to further improve the solution quality. Finally, the parametric sensitivity of the proposed algorithm has been analysed based on the Taguchi method of design of experiment. The proposed algorithm was tested through a set of typical benchmark problems of JSSP. The results demonstrated the effectiveness of the proposed algorithm for solving JSSP.     

Bi-objective mathematical model and improved algorithm for optimisation of welding shop scheduling problem

This paper addresses a bi-objective welding shop scheduling problem (BWSSP) aiming to minimise the total tardiness and the machine interaction effect. The BWSSP is a special flow-shop scheduling problem (FSP) which is characterised by the fact that more than one machine can process on one job at a certain stage. This study analyses the operation of a structural metal manufacturing plant, and includes various aspects such as job sequence, machine-number-dependent processing time, lifting up time, lifting down time and different delivery time. A novel mixed-integer programming model (MIPM) is established, which can be used to minimise the delayed delivery time and the total machine interaction effect. One machine interaction effect formula is given in this paper. In order to solve this BWSSP, an appropriate non-dominated sorting Genetic Algorithm III (NSGAIII), embedded with a restarted strategy (RNSGAIII), is proposed. The restarted strategy, which can increase the diversity of the solutions, will be triggered with a restart probability. Following the iterative process, an effective strategy is applied to reduce the interaction effect penalty, on the premise that the makespan will remain unchanged. Total five algorithms, namely NSGAII, NSGAIII, harmony search algorithm (HSA), strength Pareto evolutionary algorithm (SPEA2), and RNSGAIII are utilised to solve this engineering problem. Numerical simulations show that the improved RNSGAIII outperforms the other methods, and the Pareto solution distribution and diversity, in particular, are significantly improved.     

A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility

The traditional flexible job shop scheduling problem (FJSP) considers machine flexibility but not worker flexibility. Given the influence and potential of human factors in improving production efficiency and decreasing the cost in practical production systems, we propose a mathematical model of an extended FJSP with worker flexibility (FJSPW). A hybrid artificial bee colony algorithm (HABCA) is presented to solve the proposed FJSPW. For the HABCA, effective encoding, decoding, crossover and mutation operators are designed, and a new effective local search method is developed to improve the speed and exploitation ability of the algorithm. The Taguchi method of Design of Experiments is used to obtain the best combination of key parameters of the HABCA. Extensive computational experiments carried out to compare the HABCA with some well-performing algorithms from the literature confirm that the proposed HABCA is more effective than these algorithms, especially on large-scale FJSPW instances.     

Improved sheep flock heredity algorithm and artificial bee colony algorithm for scheduling m-machine flow shops lot streaming with equal size sub-lot problems

The objective of this paper is to develop intelligent search heuristics to solve n-jobs, m-machines lot streaming problem in a flow shop with equal size sub-lots where the objective is to minimise makespan and total flow time independently. Improved sheep flock heredity algorithm (ISFHA) and artificial bee colony (ABC) algorithms are applied to the problem above mentioned. The performance of these algorithms is evaluated against the algorithms reported in the literature. The computational analysis shows the better performance of ISFHA and ABC algorithms.     

A genetic algorithm for flexible job shop scheduling with fuzzy processing time

This paper presents a flexible job shop scheduling problem with fuzzy processing time. An efficient decomposition-integration genetic algorithm (DIGA) is developed for the problem to minimise the maximum fuzzy completion time. DIGA uses a two-string representation, an effective decoding method and a main population. In each generation, DIGA decomposes the chromosomes of the main population into a job sequencing part and a machine assigning part and independently evolves the populations of these parts. Some instances are designed and DIGA is tested and compared with other algorithms. Computational results show the effectiveness of DIGA.