الگوریتم جستجوی ممنوعه ترکیبی سریع برای مشکل عدم انتظار تولید کارگاهی

This paper describes a hybrid tabu search algorithm dedicated to a job shop problem with a no-wait constraint with a makespan criterion. The proposed here algorithm complexity is that the superior algorithm based on the tabu search technique selects parameters controlling the work of a certain constructional algorithm. This approach limits the checked solutions only to a group of solutions being able to be generated by the structural algorithm in question. It bears serious consequences both positive, for example it limits the research scope for a small fraction of relatively extremely well quality of acceptable solutions, and negative that is the lack of possibility of finding the optimal solution. In this paper numerical researches of the proposed algorithm are conducted as well as a comparative analysis with reference to the literature algorithms of the algorithm in question is made.

In this work there was analyzed a strongly NP-hard job shop problem with an additional no-wait constraint with an optimalization criteria constituting a finishing moment of all tasks performance (makespan). The presented here problem comes from a classical job shop problem by setting additional requirements concerning an acceptable solution. The difference between the analyzed problem and its classical job shop problem equivalent consists in the necessity to conduct the subsequent operations of a given task exactly in the moment of finishing their technological predecessors. This requirement is often encountered in real production processes where machined components over the course of time change their physical–chemical parameters. For example, during the steel elements’ production materials should be heated to a proper temperature in order to come next to form ready components. The formation process has to start exactly in the moment of obtaining a hot half-finished product (Wismer, 1972). Similarly, during some foodstuff’ production because of both sanitary conditions and undergoing chemical–biological processes it is essential to carry out one activity directly after another (Hall & Sriskandarajah, 1996). With reference to the complexity computational theory the classical job shop problem is classified to a group of strongly NP-hard problems, which is proved in a paper (Lenstra & Rinnooy Kan, 1979). In the same paper it is presented that in a case of adding a no-wait constraint the problem belongs to the same class too, i.e. strongly NP-hard problems. Although the theoretical complexity of both variants of the analyzed problem is the same, according to many researchers, with the practical point of view, a problem with a no-wait constraint is much more difficult. It results from the fact that the instance size, which can be solved exactly for example by the branch and bound (B&B) method, is much smaller for a variant with no-wait constraints. For example in a paper (Mascis & Pacciarelli, 2002) there was presented an algorithm finding an optimal solution in a reasonable time for an instance of a no-wait problem, in which the size did not exceed 15 tasks executed on 5 machines or 10 tasks executed on 10 machines. Besides, different kinds of approximate algorithms, an algorithm based on a tabu search technique (Macchiaroli, Mole, & Riemma, 1999), algorithm based on a technique of simulated annealing (Raaymakers & Hoogeveen, 2000) and a genetic algorithm with elements of simulated annealing (Schuster & Framinan, 2003), provide with solutions of a rather big deviation calculated relative to the reference solutions. In this work there is proposed a hybrid algorithm based on a tabu search technique dedicated to a job shop problem with no-wait constraints. The presented algorithm is regarded as a hybrid since the superior component – a tabu algorithm controls an entry parameter of a constructional algorithm generating an acceptable solution of a job shop problem with no-wait constraints. A proper algorithm’s construction generating a solution assures that a free placement of controlling parameters obtained by a superior algorithm always generates an acceptable solution. Besides, the number of different possible placements of controlling parameters is much more smaller than the number of all possible active solutions of a main problem, which limits the research scope. Generated solutions are of a relatively high quality taking into consideration the goal function’s value which results from a very calculated constructional procedure described in a further part of this work. Unfortunately, generally this approach makes finding optimal solutions, even in a case of the best selected controlling parameters, impossible. The presented here hybrid tabu search algorithm was examined numerically on a literature group of test examples. These examples are commonly used to examine new algorithms for the discussed here subject. The obtained results are compared to the best known results and confronted with GASA algorithm ( Schuster & Framinan, 2003) and the latest works of Framinan and Schuster ( Framinan and Schuster, 2006 and Schuster, 2006) taking into consideration both the algorithms’ work time and the quality of obtained solutions. The work is summarized by author’s conclusions about the proposed here algorithm.

The main achievement of this work is a very high efficiency of an algorithm. In a comparable time with a literature algorithm GASA and tabu search ( Schuster, 2006) the presented algorithm HTS finds solutions much better in a sense of optimized criterion. Conception of the algorithm proposed here gives a possibility to obtain solutions which are not able to be obtained using recent algorithms from the literature. Due to this property it was possible to obtain a new, fast, two-level algorithm (level one: generating permutations, level two: construct a solution from this ‘loading’ permutation) and to find 51 new the best known solutions for the classic benchmark instances from literature. Besides, an attention should be paid to a straight line of an algorithm HTS. This algorithm does not use in any way the essence of the problem; it only suggests the length of a schedule of the obtained result of the executive component’s function. The present further research of the authors’ work consists in making an attempt to show some relations between a loading permutation delivered through a superior component of an algorithm HTS and a length of a schedule without the necessity of its construction. According to the author finding even some statistical relations between these entities would direct a search of controlling parameters in a superior algorithm in a statistically best way. Such an HTS algorithm’s modification could significantly increase its efficiency.