Green permutation flowshop scheduling problem with sequence-dependent setup times: a case study

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

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.     

Development of a hybrid metaheuristic to minimise earliness and tardiness in a hybrid flowshop with sequence-dependent setup times

This paper presents an efficient hybrid metaheuristics for scheduling jobs in a hybrid flowshop with sequence-dependent setup times. The problem is to determine a schedule that minimises the sum of earliness and tardiness of jobs. Since this problem class is NP-hard in the strong sense, there seems to be no escape from appealing to metaheuristic procedures to achieve near-optimal solutions for real life problems. This paper proposes the hybrid metaheuristic algorithm which comprises three components: an initial population generation method based on an ant colony optimisation, a simulated annealing algorithm as an evolutionary algorithm that employs certain probability to avoid becoming trapped in a local optimum, and a variable neighbourhood search which involves three local search procedures to improve the population. A design of experiments approach is employed to calibrate the parameters of the algorithm. Results of computational tests in solving 252 problems up to 100 jobs have shown that the proposed algorithm is computationally more effective in yielding solutions of better quality than the adapted random key genetic algorithm and immune algorithm presented previously.     

Lagrangian relaxation and cut generation for sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness

The Lagrangian relaxation and cut generation technique is applied to solve sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness. The original problem is decomposed into individual job-level subproblems that can be effectively solved by dynamic programming. Two types of additional constraints for the violation of sequence-dependent setup time constraints are imposed on the decomposed subproblems in order to improve the lower bound. The decomposed subproblem with the additional setup time constraints on any subset of jobs is also effectively solved by a novel dynamic programming. Computational results show that the lower bound derived by the proposed method is much better than those of CPLEX and branch and bound for problem instances with 50 jobs and five stages with less computational effort.     

A differential evolution algorithm for the no-idle flowshop scheduling problem with total tardiness criterion

In this paper, we investigate the use of a continuous algorithm for the no-idle permutation flowshop scheduling (NIPFS) problem with tardiness criterion. For this purpose, a differential evolution algorithm with variable parameter search (vpsDE) is developed to be compared to a well-known random key genetic algorithm (RKGA) from the literature. The motivation is due to the fact that a continuous DE can be very competitive for the problems where RKGAs are well suited. As an application area, we choose the NIPFS problem with the total tardiness criterion in which there is no literature on it to the best of our knowledge. The NIPFS problem is a variant of the well-known permutation flowshop (PFSP) scheduling problem where idle time is not allowed on machines. In other words, the start time of processing the first job on a given machine must be delayed in order to satisfy the no-idle constraint. The paper presents the following contributions. First of all, a continuous optimisation algorithm is used to solve a combinatorial optimisation problem where some efficient methods of converting a continuous vector to a discrete job permutation and vice versa are presented. These methods are not problem specific and can be employed in any continuous algorithm to tackle the permutation type of optimisation problems. Secondly, a variable parameter search is introduced for the differential evolution algorithm which significantly accelerates the search process for global optimisation and enhances the solution quality. Thirdly, some novel ways of calculating the total tardiness from makespan are introduced for the NIPFS problem. The performance of vpsDE is evaluated against a well-known RKGA from the literature. The computational results show its highly competitive performance when compared to RKGA. It is shown in this paper that the vpsDE performs better than the RKGA, thus providing an alternative solution approach to the literature that the RKGA can be well suited.     

Comparisons of bi-objective genetic algorithms for hybrid flowshop scheduling with sequence-dependent setup times

This paper addresses the scheduling problems in a hybrid flowshop with two objectives of minimising the makespan and total tardiness. Since this problem is NP-hard, evolutionary algorithms based on the genetic algorithm (GA) namely; BOGAW, BOGAC, BOGAT, and BOGAS are proposed for searching the Pareto-optimal frontier. In these algorithms, we propose to generate a section of solutions for the next generation using a neighbourhood search structure on the best individual in each generation. The selection procedure selects the best chromosome based on an evaluation mechanism used in the algorithm (i.e., weighted sum, crowding distance, TOPSIS and single-objective). The aim of this paper is to clarify that the cited characteristic is efficient and it enhances the efficiency of algorithms. Therefore, we perform a comparison between the proposed algorithms to find the best alternative. Data envelopment analysis is used to evaluate the performance of approximation methods. The obtained result from the comparison shows that, BOGAC is the more efficient. To continue, since the efficiency of our idea is not clear, we compare our efficient algorithm with other efficient algorithms in the literature (namely PGA-ALS and MOGLS). The final persuasive results support the idea that BOGAC in comparison with PGA-ALS and MOGLS is more effective and efficient.     

Multiple-variable neighbourhood search for the single-machine total weighted tardiness problem

The single-machine total weighted tardiness (SMTWT) problem is a typical discrete combinatorial optimization problem in the scheduling literature. This problem has been proved to be NP hard and thus provides a challenging area for metaheuristics, especially the variable neighbourhood search algorithm. In this article, a multiple variable neighbourhood search (m-VNS) algorithm with multiple neighbourhood structures is proposed to solve the problem. Special mechanisms named matching and strengthening operations are employed in the algorithm, which has an auto-revising local search procedure to explore the solution space beyond local optimality. Two aspects, searching direction and searching depth, are considered, and neighbourhood structures are systematically exchanged. Experimental results show that the proposed m-VNS algorithm outperforms all the compared algorithms in solving the SMTWT problem.     

Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness

This paper studies the problem of scheduling flexible job shops with setup times where the setups are sequence-dependent. The objective is to find the schedule with minimum total tardiness. First, the paper develops a mathematical model in the form of mixed integer linear programming and compares it with the available model in the literature. The proposed model outperforms the available model in terms of both size complexity and computational complexity. Then, an effective metaheuristic algorithm based on iterated local search is proposed and compared with a tabu search and variable neighbourhood search algorithms proposed previously for the same problem. A complete experiment is conducted to evaluate the algorithms for performance. All the results show the superiority of the proposed algorithm against the available ones.     

Parallel machine scheduling problem with ready times,due times and sequence-dependent setup times using meta-heuristic algorithms

This article considers a parallel machine scheduling problem with ready times, due times and sequence-dependent setup times. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the weighted sum of setup times, delay times and tardy times. A mathematical model for optimal solution is derived. An in-depth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, two meta-heuristics, genetic algorithm (GA) and a new population-based evolutionary meta-heuristic called self-evolution algorithm (SEA), are proposed. The performances of the meta-heuristic algorithms are evaluated through comparison with optimal solutions using several randomly generated examples.     

A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks

This paper addresses the general assembly line balancing problem where the simple version is enriched by considering sequence-dependent setup times between tasks. Recently, Andres et al. (Andres, C., Miralles, C., and Pastor, R., 2008. Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. European Journal of Operational Research, 187, (3), 1212–1223.) proposed the type I general assembly line balancing problem with setups (GALBPS-I) and developed a mathematical model and several algorithms for solving the problem. In a similar vein, we scrutinised the GALBPS type II problem where the challenge is to find the minimum cycle time for a predefined number of work stations. To solve the problem, we develop a mathematical model and a novel simulated annealing (SA) algorithm to solve such an NP-hard problem. We then employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm and make the classical SA algorithm more efficient in terms of running time and solution quality. Computational results reflected the high efficiency of the SA algorithm in both aspects.     

Single machine scheduling problem with stochastic sequence-dependent setup times

In this study, we consider stochastic single machine scheduling problem. We assume that setup times are both sequence dependent and uncertain while processing times and due dates are deterministic. In the literature, most of the studies consider the uncertainty on processing times or due dates. However, in the real-world applications (i.e. plastic moulding industry, appliance assembly, etc.), it is common to see varying setup times due to labour or setup tools availability. In order to cover this fact in machine scheduling, we set our objective as to minimise the total expected tardiness under uncertain sequence-dependent setup times. For the solution of this NP-hard problem, several heuristics and some dynamic programming algorithms have been developed. However, none of these approaches provide an exact solution for the problem. In this study, a two-stage stochastic-programming method is utilised for the optimal solution of the problem. In addition, a Genetic Algorithm approach is proposed to solve the large-size problems approximately. Finally, the results of the stochastic approach are compared with the deterministic one to demonstrate the value of the stochastic solution.     

Unrelated parallel machine scheduling with setup times and ready times

We consider the problem of scheduling unrelated parallel machines with sequence- and machine-dependent setup times and ready times to minimise total weighted tardiness (TWT). We present a mixed integer programming model that can find optimal solutions for the studied problem. We also propose a heuristic (ATCSR_Rm) and an iterated hybrid metaheuristic (IHM) that can find optimal or nearly optimal solutions for the studied problem within a reasonable time. The proposed IHM begins with effective initial solutions, and then improves the initial solutions iteratively. The IHM integrates the principles of the attraction–repulsion mechanism within electromagnetism-like algorithms with local search. If the search becomes trapped at a local optimum, an elite search procedure is developed to help the search escape. We have compared our proposed IHM with two existing metaheuristics, tabu search (TS) and ant colony optimisation (ACO). Computational results show that the proposed IHM outperforms TS and ACO in terms of TWT for problem instances of all sizes.     

A new heuristic for the flowshop scheduling problem to minimize makespan and maximum tardiness

This paper presents a new heuristic for solving the flowshop scheduling problem that aims to minimize makespan and maximize tardiness. The algorithm is able to take into account the aforementioned performance measures, finding a set of non-dominated solutions representing the Pareto front. This method is based on the integration of two different techniques: a multi-criteria decision-making method and a constructive heuristic procedure developed for makespan minimization in flowshop scheduling problems. In particular, the technique for order preference by similarity of ideal solution (TOPSIS) algorithm is integrated with the Nawaz–Enscore–Ham (NEH) heuristic to generate a set of potential scheduling solutions. To assess the proposed heuristic's performance, comparison with the best performing multi-objective genetic local search (MOGLS) algorithm proposed in literature is carried out. The test is executed on a large number of random problems characterized by different numbers of machines and jobs. The results show that the new heuristic frequently exceeds the MOGLS results in terms of both non-dominated solutions, set quality and computational time. In particular, the improvement becomes more and more significant as the number of jobs in the problem increases.     

Using simulated annealing to schedule a flowshop manufacturing cell with sequence-dependent family setup times

This paper proposes a simulated annealing-based meta-heuristic to minimise makespan in a flowshop manufacturing cell with sequence-dependent family setup times. To escape from local minima, Cauchy function?–?rather than the Boltzmann function?–?is used during the annealing process. The effectiveness and efficiency of the proposed simulated annealing-based meta-heuristic is compared against the existing heuristics on a benchmark problem dataset used in earlier studies. These computational results show that the proposed simulated annealing-based meta-heuristic is highly effective as compared to the state-of-the-art meta-heuristics for this problem on the same benchmark instances.     

Scheduling job shop problems with sequence-dependent setup times

In this work we consider job shop problems where the setup times are sequence dependent under minimisation of the maximum completion time or makespan. We present a genetic algorithm to solve the problem. The genetic algorithm is hybridised with a diversification mechanism, namely the restart phase, and a simple form of local search to enrich the algorithm. Various operators and parameters of the genetic algorithm are reviewed to calibrate the algorithm by means of the Taguchi method. For the evaluation of the proposed hybrid algorithm, it is compared against existing algorithms through a benchmark. All the results demonstrate that our hybrid genetic algorithm is very effective for the problem.     

Minimising total weighted earliness and tardiness penalties on identical parallel machines using a fast ruin-and-recreate algorithm

This paper studies the scheduling problem of minimising total weighted earliness and tardiness penalties on identical parallel machines against a restrictive common due date. This problem is NP-hard in the strong sense and arises in many just-in-time production environments. A fast ruin-and-recreate (FR&R) algorithm is proposed to obtain high-quality solutions to this complex problem. The proposed FR&R algorithm is tested on a well-known set of benchmark test problems that are taken from the literature. Computational results provide evidence of the efficiency of FR&R, which consistently outperform existing algorithms when applied to benchmark instances. This work provides a viable alternative approach for efficiently solving this practical but complex scheduling problem.     

Scheduling identical wafer sorting parallel machines with sequence-dependent setup times using an iterated greedy heuristic

Wafer sorting is one of the most critical processes involved in semiconductor device fabrication. This study addresses the wafer sorting scheduling problem (WSSP), with minimisation of total setup time as the primary criterion and minimisation of the number of testers used as the secondary criterion. In view of the strongly NP-hard nature of this problem, a simple and effective iterated greedy heuristic is presented. The performance of the proposed heuristic is empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor. The experimental results show that the proposed heuristic is effective and efficient as compared to the state-of-art algorithms developed for the same problem. It is believed that this study has developed an approach that is easy to comprehend and satisfies the practical needs of wafer sorting.     

Hybrid flowshop scheduling with family setup time and inconsistent family formation

This research considers a hybrid flowshop scheduling problem where jobs are organised in families according to their machine settings and tools. The family setup time arises when a machine shifts from processing one job family to another. The problem is compounded by the challenges that the formation of job families is different in different stages and only a limited number of jobs can be processed within one setup. This type of problem is common in the production process of standard metal components. This paper aims to propose two approaches to solve this problem. One is a metaheuristic in the form of a genetic algorithm and the other is a heuristic. The proposed approaches are compared and contrasted against the two relevant metaheuristic and heuristic adapted from solving a generalised sequence-dependent setup flowshop problem. Comparative results indicate that the proposed genetic algorithm has better performance on minimising makespan and the heuristic is more effective on reducing family setup time.