جستجوی ممنوعه برای به حداقل رساندن تاخیر کل در یک تولید کارگاهی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|18886||2000||10 صفحه PDF||سفارش دهید||5051 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : International Journal of Production Economics, Volume 63, Issue 2, 15 January 2000, Pages 131–140
This paper presents a tabu search approach to minimize total tardiness for the job shop scheduling problem. The method uses dispatching rules to obtain an initial solution and searches for new solutions in a neighborhood based on the critical paths of the jobs. Diversification and intensification strategies are suggested. For small problems the solutions’ quality is evaluated against optimal solution values and for large problems the tabu search performance is compared with two heuristics proposed in the literature.
The classic job shop environment can be defined by a set of M machines and a set of J jobs, with each job consisting of an ordered sequence of M operations. Each operation is processed on a single machine and preemption is not allowed. Each machine can process only one operation at a time, with different operations of the same job processed on different machines. The problem is to find a schedule, i.e., an assignment of the operations to time intervals on the machines to minimize one or more criteria. It is well known that the scheduling problem in a job shop can be represented by a disjunctive graph . The graph can be described as follows. For each operation of each job, there corresponds a node with a weight equal to the processing time involved. For each job a set of arcs is created to represent the ordered sequence of operations of that job. Two artificial nodes with zero weight are included to represent the initial and final operations. These nodes are linked to the nodes corresponding to the first and last operations of each job, respectively. The nodes corresponding to the operations to be executed on the same machine are connected by disjunctive arcs. The direction of such arcs define the precedence of operations on the machines. Fig. 1 shows a disjunctive graph for a problem with three jobs and four machines M1, M2, M3 and M4. Full-size image (11 K) Fig. 1. Disjunctive graph. Figure options When the direction of the disjunctive arcs is chosen, a directed graph is obtained. It is then possible to calculate the critical path for each job, which corresponds to the longest path from node 0 to its final node, for example, the final node for job 2 is node 8. This path determines the completion time of the job, and consequently any tardiness involved. The objective of this paper is to determine a schedule which minimizes total tardiness in relation to job due dates. A heuristic method, which starts from an initial solution obtained through the application of dispatching rules and tries to find new and better solutions through the tabu search method, is developed. Diversification and intensification strategies are used in order to obtain better solutions. Since the classic problem of job shop scheduling is one of the most difficult problems of combinatorial optimization , research has been directed to heuristic methods of solution. Various heuristic methods have been developed for problems in which the makespan is considered to be a measurement of performance, including tabu search , ,  and , simulated annealing , and genetic algorithms  and  as well as others designed specifically for the problem  and . For problems involving due dates and, consequently with tardiness, however, the literature is quite scarce. Dispatching rules are frequently utilized because they are fast , , ,  and , although their performance is generally unpredictable. More elaborate heuristic methods are suggested in  and . He et al.  proposed an improvement method which starts from an initial solution and tries to move backwards specific operations of tardy jobs in order to reduce total tardiness. The method stops when no improvement moves exist. Tests were performed on problems involving 60, 70, 80, 90, 100 jobs and 30 machines and the gains in relation to the initial solutions, given by five dispatching rules, ranged from 1.8% to 4.3%. Raman and Talbot  present a procedure to improve the initial solution generated by the modified operation due date (MOD) dispatching rule . For each machine, an attempt is made to improve the solution through an appropriate alteration of the operation due dates relative to tardy jobs. For each alteration, a new schedule is then obtained by the application of the same rule. The method stops when the solution can not be improved or a prescribed computational time is reached. Tests were carried out for problems with 15, 35 jobs and 5, 10 machines and the average improvement over six dispatching rules was 12.7%. The present paper suggests a new approach to the problem of minimizing total tardiness in a job shop using the technique of tabu search. For small problems involving up to seven jobs and five machines the solutions’ quality is evaluated against optimal solutions. For larger problems the tabu search performance is compared with the heuristics methods proposed by He et al.  and Raman and Talbot . The paper is organized as follows. The application of tabu search to the job shop problem suggested in the literature is presented in Section 2. The method developed is described in Section 3. Section 4 presents diversification and intensification strategies as well as computational tests. Conclusions are presented in Section 5.
نتیجه گیری انگلیسی
The objective of this paper was to apply the tabu search method to the problem of minimizing tardiness in a job shop. Strategies of diversification and intensification were incorporated to the short-term memory tabu search and have shown to be effective for obtaining good solutions. For larger instances, tabu search outperformed two heuristics from the literature. For small instances, tabu search provides optimal solutions in 72.5% of the cases and the degree of improvement achieved over the MDD solution leads to high-quality solutions.