Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising.     

Effective heuristics for the blocking flowshop scheduling problem with makespan minimization

The blocking flowshop scheduling problem with makespan criterion has important applications in a variety of industrial systems. Heuristics that explore specific characteristics of the problem are essential for many practical systems to find good solutions with limited computational effort. This paper first presents two simple constructive heuristics, namely weighted profile fitting (wPF) and PW, based on the profile fitting (PF) approach of McCormick et al. [Sequencing in an assembly line with blocking to minimize cycle time. Operations Research 1989;37:925-36] and the characteristics of the problem. Then, three improved constructive heuristics, called PF-NEH, wPF-NEH, and PW-NEH, are proposed by combining the PF, wPF, and PW with the enumeration procedure of the Nawaz-Enscore-Ham (NEH) heuristic [A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA-International Journal of Management Science 1983;11:91-5] in an effective way. Thirdly, three composite heuristics i.e., PF-NEH_LS, wPF-NEH_LS, and PW-NEH_LS, are developed by using the insertion-based local search method to improve the solutions generated by the constructive heuristics. Computational simulations and comparisons are carried out based on the well-known flowshop benchmarks of Taillard [Benchmarks for basic scheduling problems. European Journal of Operation Research 1993;64:278-85] that are considered as blocking flowshop instances. The results show that the presented constructive heuristics perform significantly better than the existing ones, and the proposed composite heuristics further improve the presented constructive heuristics by a considerable margin. In addition, 17 new best-known solutions for Taillard benchmarks with large scale are found by the presented heuristics.     

Heuristics for scheduling in a flowshop with setup,processing and removal times separated

The problem of scheduling in a flowshop, where setup, processing and removal times are separable, is considered with the objective of minimizing makespan. Heuristic algorithms are developed by the introduction of simplifying assumptions into the scheduling problem under study. An improvement method is incorporated in the heuristics to enhance the quality of their solutions. The proposed heuristics and an existing heuristic are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various values of parameters are presented.     

New high performing heuristics for minimizing makespan in permutation flowshops

The well-known NEH heuristic from Nawaz, Enscore and Ham proposed in 1983 has been recognized as the highest performing method for the permutation flowshop scheduling problem under the makespan minimization criterion. This performance lead is maintained even today when compared against contemporary and more complex heuristics as shown in recent studies. In this paper we show five new methods that outperform NEH as supported by careful statistical analyses using the well-known instances of Taillard. The proposed methods try to counter the excessive greediness of NEH by carrying out re-insertions of already inserted jobs at some points in the construction of the solution. The five proposed heuristics range from extensions that are slightly slower than NEH in most tested instances to more comprehensive methods based on local search that yield excellent results at the expense of some added computational time. Additionally, NEH has been profusely used in the flowshop scheduling literature as a seed sequence in high performing metaheuristics. We demonstrate that using some of our proposed heuristics as seeds yields better final results in comparison.     

Analysis of antithetic sequences in flowshop scheduling to minimize makespan

The antithetic properties of flowshop sequences are investigated to improve the classical Monte Carlo method for solving the n -job, m -machine problem with minimization of makespan. The major issues considered are (1) establishing a negative correlation of the makespan values of forward and reverse sequences; (2) developing the Antithetical Monte Carlo (AMC) method, which can be used to quickly estimate the mean of the makespan distribution by exploiting the antithetic property of sequences; (3) using AMC to find low makespan values; (4) determining a threshold value of makespan beyond which it would be likely to find an optimal or near optimal makespan when reversing a sequence. Statistical tests indicate that the performance of AMC is superior to that of the classical Monte Carlo method. Possible applications of this concept are discussed including extensions to other mathematical problems with antithetic properties.     

Makespan and workstation utilization minimization in a flowshop with operations flexibility

Production environments where there are more tasks than workstations and any task can be assigned to any workstation are examples of operations flexibility. This paper investigates the benefits of operations flexibility in a flowshop when the goals are to minimize the makespan and workstation utilization. Furthermore, machine dominance principles are extended to the case of a flowshop with operations flexibility. The proposed heuristic framework comprises of two phases, allocation of operations to workstations and generation of job sequencing. In addition, an improvement procedure based on simulated annealing is implemented for this problem. The experimental results identify the effects of the experimental factors; show the significance of the heuristic factor; and demonstrate the tradeoff between the two performance criteria.     

A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation

The hybrid flowshop scheduling (HFS) problem with the objective of minimising the makespan has important applications in a variety of industrial systems. This paper presents an effective discrete artificial bee colony (DABC) algorithm that has a hybrid representation and a combination of forward decoding and backward decoding methods for solving the problem. Based on the dispatching rules, the well-known NEH heuristic, and the two decoding methods, we first provide a total of 24 heuristics. Next, an initial population is generated with a high level of quality and diversity based on the presented heuristics. A new control parameter is introduced to conduct the search of employed bees and onlooker bees with the intention of balancing the global exploration and local exploitation, and an enhanced strategy is proposed for the scout bee phase to prevent the algorithm from searching in poor regions of the solution space. A problem-specific local refinement procedure is developed to search for solution space that is unexplored by the honey bees. Afterward, the parameters and operators of the proposed DABC are calibrated by means of a design of experiments approach. Finally, a comparative evaluation is conducted, with the best performing algorithms presented for the HFS problem under consideration, and with adaptations of some state-of-the-art metaheuristics that were originally designed for other HFS problems. The results show that the proposed DABC performs much better than the other algorithms in solving the HFS problem with the makespan criterion.     

Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem

In this work three genetic algorithms are presented for the permutation flowshop scheduling problem with total tardiness minimisation criterion. The algorithms include advanced techniques like path relinking, local search and a procedure to control the diversity of the population. We also include a speed up procedure in order to reduce the computational effort needed for the local search technique, which results in large CPU time savings. A complete calibration of the different parameters and operators of the proposed algorithms by means of a design of experiments approach is also given. We carry out a comparative evaluation with the best methods that can be found in the literature for the total tardiness objective, and with adaptations of other state-of-the-art methods originally proposed for other objectives, mainly makespan. All the methods have been implemented with and without the speed up procedure in order to test its effect. The results show that the proposed algorithms are very effective, outperforming the remaining methods of the comparison by a considerable margin.     

Heuristic algorithms for the two-machine flowshop with limited machine availability

The paper studies a flowshop scheduling problem where machines are not available in given time intervals. The objective is to minimize the makespan. The problem is known to be NP-hard for two machines. We analyze constructive and local search based heuristic algorithms for the two-machine case. The algorithms are tested on easy and difficult test problems with up to 100 jobs and 10 intervals of non-availability. Computational results show that the algorithms perform well. For many problems an optimum solution is found.     

Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm

The blocking flowshop scheduling problem has a strong industrial background but is under-represented in the research literature. In this study, a revised artificial immune system (RAIS) algorithm based on the features of artificial immune systems and the annealing process of simulated annealing algorithms was presented to minimize the makespan in a blocking flowshop. To validate the performance of the proposed RAIS algorithm, computational experiments and comparisons were conducted on the well-known benchmark problems of Taillard used in earlier studies. The experimental results show that the proposed RAIS algorithm outperforms the state-of-art algorithms on the same benchmark problem data set.     

An iterated greedy algorithm for the flowshop scheduling problem with blocking

This paper proposes an iterated greedy algorithm for solving the blocking flowshop scheduling problem for makespan minimization. Moreover, it presents an improved NEH-based heuristic, which is used as the initial solution procedure for the iterated greedy algorithm. The effectiveness of both procedures was tested on some of Taillard’s benchmark instances that are considered to be blocking flowshop instances. The experimental evaluation showed the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. In addition, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

A pairwise interchange algorithm for parallel machine scheduling

This paper considers the problem of non-preemptive scheduling n tasks on m identical parallel processors to minimize makespan for simultaneous arrivals. Based on a pairwise interchange method, an efficient algorithm ispresented which is able to give a near-optimal schedule in a short time through suitable pairwise interchange between tasks, after an initial solution is constructed. The behaviour of the algorithm is discussed. Testing results prove its high performance in comparison with available simple heuristic procedures. Finally, the algorithm is generalized for the problems of non-identical processors and non-simultaneous arrivals.     

Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the makespan when every job has a positive tail. We propose a polynomial approximation algorithm with a worst-case performance ratio of 3/2 for this problem. We show that this bound is tight. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm) by exploiting the well-known approach of Ibarra and Kim (J. ACM 22:463–468, 1975). Such an FPTAS is strongly polynomial. The obtained results outperform the previous polynomial approximation algorithms for this problem.     

An efficient tabu search algorithm for the single- machine mean tardiness problem

In this paper, an efficient tabu search algorithm is prepared for solving the single-machine mean tardiness problem. The proposed implementation of the tabu search approach suggests simple techniques for generating neighbourhoods of a given sequence and a combined scheme for intensification and diversification. The tabu search method is shown to produce results very close to the optimal solution using randomly generated problems with varying degrees of difficulty.     

On the NEH heuristic for minimizing the makespan in permutation flow shops

Over the last 20 years the NEH heuristic of Nawaz, Enscore, and Ham published in this journal has been commonly regarded as the best heuristic for minimizing the makespan in permutation flow shops. In recent years some authors claimed to develop new heuristics that are competitive or outperform NEH. Our study reveals that these claims are not justified. We also address the issue of a fair comparison of the NEH results with those obtained by metaheuristics. Finally we conduct a thorough analysis of NEH leading to its modification which secures the optimality in the two-machine case and improves the general performance.     

One-machine scheduling to minimize mean tardiness with minimum number tardy

In this paper the one-machine scheduling problem with the objective of minimizing the mean tardiness subject to maintaining a prescribed number of tardy jobs is analysed. An algorithm for solving this problem is presented. It is proved that the schedule generated by the proposed algorithm is indeed optimal.     

An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem

In the no-idle flowshop, machines cannot be idle after finishing one job and before starting the next one. Therefore, start times of jobs must be delayed to guarantee this constraint. In practice machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine in between jobs. This has important ramifications in the modern industry including fiber glass processing, foundries, production of integrated circuits and the steel making industry, among others. However, to assume that all machines in the shop have this no-idle constraint is not realistic. To the best of our knowledge, this is the first paper to study the mixed no-idle extension where only some machines have the no-idle constraint. We present a mixed integer programming model for this new problem and the equations to calculate the makespan. We also propose a set of formulas to accelerate the calculation of insertions that is used both in heuristics as well as in the local search procedures. An effective iterated greedy (IG) algorithm is proposed. We use an NEH-based heuristic to construct a high quality initial solution. A local search using the proposed accelerations is employed to emphasize intensification and exploration in the IG. A new destruction and construction procedure is also shown. To evaluate the proposed algorithm, we present several adaptations of other well-known and recent metaheuristics for the problem and conduct a comprehensive set of computational and statistical experiments with a total of 1750 instances. The results show that the proposed IG algorithm outperforms existing methods in the no-idle and in the mixed no-idle scenarios by a significant margin.     

Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities

This paper considers a single-machine scheduling with a position-dependent aging effect described by a power function under maintenance activities and variable maintenance duration considerations simultaneously. We examine two models of the maintenance duration in this study. The objective is to find jointly the optimal maintenance frequency, the optimal maintenance positions, and the optimal job sequences to minimize the makespan of all jobs. We provided polynomial time solution algorithms for all the studied problems.     

An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan

Motivated by the existence of an APTAS (Asymptotic PTAS) for bin packing problem, we consider the batch scheduling problem with nonidentical job sizes to minimize makespan. For the proportional special version, i.e., there exists a fixed number α such that p _j =α s _j for every 1≤j≤n, we first present a lower bound of 3/2 for the approximation ratio and then design an APTAS. Supported by NNSF of China (No.10671108).