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 shuffled frog-leaping algorithm for job shop scheduling with outsourcing options

In this paper, job shop scheduling problem with outsourcing options is considered and a novel shuffled frog-leaping algorithm (SFLA) is presented to minimise total tardiness under condition that total outsourcing cost does not exceed a given upper bound. In SFLA, a tournament selection-based method is used to decompose the whole population into some memeplexes, the search process in each memeplex is done on the best solution of the memeplex and composed of the global search step and the multiple neighbourhood search step. SFLA is tested on a number of instances and compared with some methods from the literature. Computational results validate the promising performance of SFLA on the considered problem.     

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.     

A shuffled frog-leaping algorithm for flexible job shop scheduling with the consideration of energy consumption

Flexible job shop scheduling problem (FJSP) has been extensively investigated and objectives are often related to time. Energy-related objective should be considered fully in FJSP with the advent of green manufacturing. In this study, FJSP with the minimisation of workload balance and total energy consumption is considered and the conflicting between two objectives is analysed. A shuffled frog-leaping algorithm (SFLA) is proposed based on a three-string coding approach. Population and a non-dominated set are used to construct memeplexes according to tournament selection and the search process of each memeplex is done on its non-dominated member. Extensive experiments are conducted to test the search performance of SFLA and computational results show the conflicting between two objectives of FJSP and the promising advantages of SFLA on the considered FJSP.     

An adaptive scheduling algorithm for a parallel machine problem with rework processes

The development of a scheduling methodology for a parallel machine problem with rework processes is presented in this paper. The problem is to make a schedule for parallel machines with rework probabilities, due-dates, and sequence dependent setup times. Two heuristics are developed based on a dispatching algorithm and problem-space-based search method. In order to evaluate the efficacy of the proposed algorithms, six performance indicators are considered: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of tardy jobs, and the number of reworks. This paper shows how these algorithms can adaptively capture the characteristics of manufacturing facilities for enhancing the performance under changing production environments. Extensive experimental results show that the proposed algorithms give very efficient performance in terms of computational time and each objective value.     

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.     

Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times

In this paper, we address the two stage assembly flow-shop problem with multiple non-identical assembly machines in stage two to minimise weighted sum of makespan and mean completion time. Also, sequence dependent setup times are considered for the first stage. This problem is a generalisation of previously proposed two stage assembly flow-shop problems (TSAFSP). In many real world industrial and production systems, there is more than one assembly machine to assemble job components. After extending a mathematical mixed-integer linear programming model to solve the problem, we use GAMS software. The TSAFSP has been known as NP-hard. Therefore, our more general problem is NP-hard too and so for large sized problems the right way to proceed is with the use of heuristic algorithms. So in this paper a hybrid VNS heuristic, which is a combination of the variable neighbourhood search (VNS) algorithm and a novel heuristic is developed and its solutions compared with solutions obtained by GAMS. Computational experiments reveal that the hybrid VNS heuristic performs much better than GAMS with respect to the percentage errors and run times.     

Speeding up a Rollout algorithm for complex parallel machine scheduling

Rollout methodology is a constructive metaheuristic algorithm and its main characteristics are its modularity, the adaptability to different objectives and constraints and the easiness of implementation. Multi-heuristic Rollout extends the Rollout by incorporating several constructive heuristics in the Rollout framework and it is able to easily incorporate human experience inside its research patterns to fulfil complex requirements dictated by the application at hand. However, a drawback for both Rollout and multi-heuristic Rollout is often represented by the required computation time. This paper proposes some alternatives of the full multi-heuristic Rollout algorithm aimed at improving the efficiency by reducing the computational effort while preserving the effectiveness. Namely, we propose dynamic heuristics pruning and candidates reduction strategies. As illustrative case studies, we analyse complex deterministic identical parallel machine scheduling problems showing how Rollout procedures can be used to tackle several additional constraints arising in real contexts. More specifically, we considered both standard (batch production, family set-ups, release, due dates, etc.) and non-standard (machine unavailabilities, maximum campaign size) scheduling constraints. An extensive campaign of computational experiments shows the behaviour of the multi-heuristic Rollout approach and the effectiveness of the different proposed speed-up methods.     

Mathematical modelling and optimisation of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines

This paper investigates an energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines (HFSP-UPM) with the energy-saving strategy of turning off and on. We first analyse the energy consumption of HFSP-UPM and formulate five mixed integer linear programming (MILP) models based on two different modelling ideas namely idle time and idle energy. All the models are compared both in size and computational complexities. The results show that MILP models based on different modelling ideas vary dramatically in both size and computational complexities. HFSP-UPM is NP-Hard, thus, an improved genetic algorithm (IGA) is proposed. Specifically, a new energy-conscious decoding method is designed in IGA. To evaluate the proposed IGA, comparative experiments of different-sized instances are conducted. The results demonstrate that the IGA is more effective than the genetic algorithm (GA), simulating annealing algorithm (SA) and migrating birds optimisation algorithm (MBO). Compared with the best MILP model, the IGA can get the solution that is close to an optimal solution with the gap of no more than 2.17% for small-scale instances. For large-scale instances, the IGA can get a better solution than the best MILP model within no more than 10% of the running time of the best MILP model.     

A hybrid genetic-immune algorithm with improved lifespan and elite antigen for flow-shop scheduling problems

In this paper, a hybrid genetic-immune algorithm (HGIA) is proposed to reduce the premature convergence problem in a genetic algorithm (GA) in solving permutation flow-shop scheduling problems. A co-evolutionary strategy is proposed for efficient combination of GA and an artificial immune system (AIS). First, the GA is adopted to generate antigens with better fitness, and then the population in the last generation is transformed into antibodies in AIS. A new formula for calculating the lifespan of each antibody is employed during the evolution processes. In addition, a new mechanism including T-cell and B-cell generation procedures is applied to produce different types of antibodies which will be merged together. The antibodies with longer lifespan will survive and enter the next generation. This co-evolutionary strategy is very effective since chromosomes and antibodies will be transformed and evolved dynamically. The intensive experimental results show the effectiveness of the HGIA approach. The hybrid algorithm can be further extended to solve different combinatorial problems.     

Robust makespan minimisation in identical parallel machine scheduling problem with interval data

Parallel machine scheduling problems are commonly encountered in a wide variety of manufacturing environments and have been extensively studied. This paper addresses a makespan minimisation scheduling problem on identical parallel machines, in which the specific processing time of each job is uncertain, and its probability distribution is unknown because of limited information. In this case, the deterministic or stochastic scheduling model may be unsuitable. We propose a robust (min–max regret) scheduling model for identifying a robust schedule with minimal maximal deviation from the corresponding optimal schedule across all possible job-processing times (called scenarios). These scenarios are specified as closed intervals. To solve the robust scheduling problem, which is NP-hard, we first prove that a regret-maximising scenario for any schedule belongs to a finite set of extreme point scenarios. We then derive two exact algorithms to optimise this problem using a general iterative relaxation procedure. Moreover, a good initial solution (optimal schedule under a mid-point scenario) for the aforementioned algorithms is discussed. Several heuristics are developed to solve large-scale problems. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines

Majority of researches in no-wait flowshop scheduling assume that there is only one machine at each stage. But, factories commonly duplicate machines in parallel for each operation. In this case, they balance the speed of the stages, increase the throughput of the shop floor and reduce the impact of bottleneck stages. Despite their importance, there is no paper to study the general no-wait flowshop with parallel machines. This paper studies this problem where the objective is to minimise makespan. Since there is no mathematical model for the problem, we first mathematically formulate it in form of two mixed integer linear programming models. By the models, the small instances are optimally solved. We then propose a novel hunting search metaheuristic algorithm (HSA) to solve large instances of the problem. HSA is derived based on a model of group hunting of animals when searching for food. A set of experimental instances are carried out to evaluate the algorithm. The algorithm is carefully evaluated for its performance against an available algorithm by means of statistical tools. The related results show that the proposed HSA provides sound performance comparing with other algorithms.     

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.     

Minimising interference for scheduling two parallel machines with a single server

In this paper, we consider the problem of scheduling a set of jobs on two parallel machines with set-up times. The set-up has to be performed by a single server. The objective is to minimise the forced idle time. The problem of minimising the forced idle time (interference problem) is known to be unary NP-hard for the case of two machines and equal set-up and arbitrary processing times. We propose a mixed integer linear programming model, which describes a special class of schedules where the jobs from a list are scheduled alternatively on the machines, and a heuristic algorithm is tested on instances with up to 100,000 jobs. The computational results indicate that the algorithm has an excellent performance even for very large instances, where mostly an optimal solution is obtained within a very small computational time.     

Parallel machine scheduling with preference of machines

This paper considers a scheduling problem in the manufacturing of anodic electro-etching aluminium foil. To reduce cost and increase efficiency, the manufacturer of aluminium foil usually designs the equipment for electro-etching of aluminium foil into specialised equipment that is dedicated to produce high voltage or medium voltage aluminium foil based on the range the aluminium foil can bear. Nevertheless, high voltage equipment can be used to produce medium voltage aluminium foil with longer processing time, and vice versa. The problem is to schedule jobs on the high and medium voltage equipment, each having several pieces in parallel, with setup times to minimise to the total completion time. In this paper, we propose a three-stage heuristic for this problem and computationally evaluate the performance of the heuristic in comparison to a heuristic for unrelated parallel machines and a branch-and-bound algorithm.     

An improved imperialist competitive algorithm based photolithography machines scheduling

Abstract: Photolithography machine is one of the most expensive equipment in semiconductor manufacturing system, and as such is often the bottleneck for processing wafers. This paper focuses on photolithography machines scheduling with the objective of total completion time minimisation. In contrast to classic parallel machines scheduling, it is characterised by dynamical arrival wafers, re-entrant process flows, dedicated machine constraints and auxiliary resources constraints. We propose an improved imperialist competitive algorithm (ICA) within the framework of a rolling horizon strategy for the problem. We develop a variable time interval-based rolling horizon strategy to decide the scheduling point. We address the global optimisation in every local scheduling by proposing a mixed cost function. Moreover, an adaptive assimilation operator and a sociopolitical competition operator are used to prevent premature convergence of ICA to local optima. A chaotic sequence-based local search method is presented to accelerate the rate of convergence. Computational experiments are carried out comparing the proposed algorithm with ILOG CPLEX, dispatching rules and meta-heuristic algorithms in the literature. It is observed that the algorithm proposed shows an excellent behaviour on cycle time minimisation while with a good on time delivery rate and machine utilisation rate.     

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.     

An effective estimation of distribution algorithm for the flexible job-shop scheduling problem with fuzzy processing time

Considering the fuzzy nature of the data in real-world scheduling, an effective estimation of distribution algorithm (EDA) is proposed to solve the flexible job-shop scheduling problem with fuzzy processing time. A probability model is presented to describe the probability distribution of the solution space. A mechanism is provided to update the probability model with the elite individuals. By sampling the probability model, new individuals can be generated among the search region with promising solutions. Moreover, a left-shift scheme is employed for improving schedule solution when idle time exists on the machine. In addition, some fuzzy number operations are used to calculate scheduling objective value. The influence of parameter setting is investigated based on the Taguchi method of design of experiment, and a suitable parameter setting is suggested. Numerical testing results and comparisons with some existing algorithms are provided, which demonstrate the effectiveness of the proposed EDA.     

Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times

This paper focuses on an identical parallel machine scheduling problem with minimising total tardiness of jobs. There are two major issues involved in this scheduling problem; (1) jobs which can be split into multiple sub-jobs for being processed on parallel machines independently and (2) sequence-dependent setup times between the jobs with different part types. We present a novel mathematical model with meta-heuristic approaches to solve the problem. We propose two encoding schemes for meta-heuristic solutions and three decoding methods for obtaining a schedule from the meta-heuristic solutions. Six different simulated annealing algorithms and genetic algorithms, respectively, are developed with six combinations of two encoding schemes and three decoding methods. Computational experiments are performed to find the best combination from those encoding schemes and decoding methods. Our findings show that the suggested algorithm provides not only better solution quality, but also less computation time required than the commercial optimisation solvers.     

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.