برخی از الگوریتم های هیوریستیک برای به حداقل رساندن تاخیر در یک فروشگاه جریان همراه با مسدود کردن

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.

This paper analyzes the flowshop scheduling problem with blocking between machines. This environment is characterized by processing n jobs on m machines in the same order, that is, the jth operation of every job must always be conducted on machine j. The processing times of each job on each machine are known. Since there is no buffer storage between machines, queues of jobs waiting in the system for their next operation are not allowed. A job completed on one machine blocks it until the next machine is available for processing. Note that this environment is different from the no-wait flowshop environment. In the latter, there is no machine blocking: once a job is started on the first machine, it must be continuously processed (without interruption) until its completion on the last machine. According to Hall and Sriskandarajah [1], blocking can be related to the production process itself. Some examples of blocking can be found in concrete block manufacturing, which does not allow stock in some stages of the manufacturing process [2], and in a robotic cell, where a job may block a machine while waiting for the robot to pick it up and move it to the next stage [3]. The scheduling performance measure considered in this paper is the minimization of the total tardiness of jobs. The tardiness criterion is of great importance in manufacturing systems because certain costs are incurred when a job is not completed by its due date. These costs include: penalty clauses in the contract, loss of goodwill resulting in an increased probability of losing the customer for some or all future jobs, and a damaged reputation which will turn other customers away [4]. The tardiness of a job can be computed using the recursive equations presenteded by Pinedo [5]. Let t1,t2,…,ti,…,tnt1,t2,…,ti,…,tn be the sequence to be evaluated, where titi represents the job that occupies the ith position in the considered sequence. Let M1,M2,…,Mj,…,MmM1,M2,…,Mj,…,Mm be the ordered sequence of machines, pkjpkj the processing time of job k on machine MjMj, and dkdk the due date of job k. Let Dti,0Dti,0 denote the start time of job titi on the first machine and Dti,jDti,j the departure time of job titi on machine MjMj. The departure times of each job on each machine are given by the following expressions: equation(1) Dt1,0=0,Dt1,0=0, Turn MathJax on equation(2) View the MathML sourceDt1,j=∑q=1jpt1,q,j=1,…,m-1, Turn MathJax on equation(3) View the MathML sourceDti,0=Dt(i-1),1i=2,…,n, Turn MathJax on equation(4) View the MathML sourceDti,j=max(Dti,j-1+pti,j,Dt(i-1),j+1)i=2,…,n,j=1,…,m-1, Turn MathJax on equation(5) View the MathML sourceDti,m=Dti,m-1+pti,mi=1,…,n. Turn MathJax on Since the completion times of the jobs are known (Dti,j)(Dti,j), the total tardiness is given by equation(6) View the MathML sourceT=∑i=1nmax(Dti,m-dti,0). Turn MathJax on The level of difficulty of the problem can be assessed using the particular case of a single machine, which is NP-hard for the tardiness criterion [6]. Moreover, it can be shown that the decision version of the flowshop problem with blocking and three machines minimizing the makespan criterion, which is NP-hard in the strong sense, is reducible to the decision version of this problem considering the minimization of the total tardiness (to know whether the makespan is less than or equal to a threshold value y, one needs to define dk=ydk=y for all k=1…nk=1…n and to solve the corresponding tardiness decision problem). See Lenstra et al. [7] for similar cases. The research on flowshop with blocking is not extensive. An overview of the literature on the makespan criterion follows. A good review can be found in Hall and Sriskandarajah [1], who proved that this problem with three machines is NP-hard in the strong sense. In a previous work, Leisten [8] presented a more complex proof that the equivalent decision version of this problem is NP-complete. This author reduced the three-dimensional matching problem to a special case of the flowshop problem with blocking and three machines. Among heuristic approaches, McCormick et al. [9] developed an algorithm, known as Profile Fitting, which tries to initially sequence jobs that lead to the minimum sum of idle times and blocking times on machines. A more comprehensive approach is presented by Leisten [10], who compares heuristics adapted from cases of no-wait, unlimited buffers, limited buffers, and two specially designed heuristics which attempt to optimize the utilization of the available buffer storage. The author concludes that the heuristics allowing job passing did not lead to good solutions and that the NEH algorithm proposed by Nawaz et al. [11] performs better. Ronconi [12] suggests three constructive heuristics, including a combination of the Profile Fitting heuristic and the enumeration procedure used by the NEH algorithm. The proposed methods outperform the NEH algorithm in problems involving up to 500 jobs and 20 machines. Abadi et al. [13] propose a heuristic for minimizing the steady state cycle time to repetitively produce a minimal part set in an m-machine blocking flowshop. The key idea is slowing down operations in order to make a connection between the no-wait flowshop, in which jobs do not wait between operations, and the blocking flowshop. This method can also be applied to minimize the makespan. Caraffa et al. [14] used this concept to develop a genetic algorithm (GA) to minimize this criterion. Computational results indicate that the proposed method shows a better performance than the heuristic developed by Abadi et al. [13]. More recently, Grabowski and Pempera [15] develop a tabu search algorithm that utilizes multimoves to accelerate the convergence of the method. The proposed strategy achieved better results than the GA proposed by Caraffa et al. [14]. Furthermore, this methodology was able to improve the reference makespans provided by the branch-and-bound algorithm (B&B) presented by Ronconi [16]. As far as we know, few studies deal with the total tardiness criterion in the flowshop environment with blocking. Armentano and Ronconi [17] suggest a tabu search-based heuristic with an initial solution given by the algorithm LBNEH [18], which exploits characteristics of the tardiness criterion. Diversification, intensification and neighborhood restriction strategies were also evaluated. The authors report computational tests with problems up to 50 jobs. In another work, Ronconi and Armentano [19] present a B&B algorithm to minimize total tardiness where fixed jobs are placed at the end of the complete sequence. They propose a lower bound for this criterion and, as a by-product, lower bounds for the makespan and for the sum of job completion times. In this paper we propose heuristic approaches for the minimization of the total tardiness of jobs in a flowshop with blocking in-process. We present a constructive heuristic that explores the non-existence of intermediate buffers, as well as the characteristics related to the tardiness criterion. The small computational effort of such strategy, which is valuable in some practical applications, is one of the reasons that motivated this study. A GRASP-based (greedy randomized adaptive search procedure) heuristic is also proposed. Furthermore, the metaheuristic is coupled with a path relinking strategy to search for better outcomes. We assessed the performance of the proposed methods through a comparative study with other methods described in the literature. This paper is organized as follows. Section 2 presents the constructive heuristic, while Section 3 explains how the GRASP metaheuristic was adapted for the focused problem. An additional strategy based on path relinking is also described. Section 4 shows computational experiments with the constructive heuristic, the basic implementation of GRASP and the inclusion of path relinking. The last section summarizes the main results.

In this paper we studied the minimization of the total tardiness in a flowshop with blocking scheduling. First, we proposed a constructive heuristic called FPDNEH. In a comparison of the FPDNEH against the LBNEH algorithm, known as the best constructive heuristic for this problem, the proposed algorithm presented an average improvement of 11.11% and achieved better results in 336 of the 480 tested problems. This behavior is probably due to the fact that the dispatch rule FPD explores the non-existence of intermediate buffers, as well as the characteristics related to the tardiness criterion. Then, we developed a GRASP-based heuristic to obtain better solutions within a reasonable period of time. The basic version presented an overall average improvement of 30.98% in comparison with the constructive heuristic, and better results in 475 of the 480 test-problems. Furthermore, the association of GRASP with a path relinking strategy was able to improve the performance of the metaheuristic for some problems, with approximately the same running time. Finally, the comparison with optimal solutions for small problems showed that all versions can yield good results, especially GRASP with path relinking. As a future research effort, it would be interesting to extend the ideas presented in this paper to the flowshop with blocking, aiming to minimize the total earliness and tardiness cost.