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

In this paper we address a hybrid flow shop scheduling problem considering the minimization of the sum of the total earliness and tardiness penalties. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, we propose an ant colony optimization method to deal with this problem. Our proposed method has several features, including some heuristics that specifically take into account both earliness and tardiness penalties to compute the heuristic information values. The performance of our algorithm is tested by numerical experiments on a large number of randomly generated problems. A comparison with solutions performance obtained by some constructive heuristics is presented. The results show that the proposed approach performs well for this problem.

The hybrid flow shop (HFS), also called multiprocessor or flow shop with parallel machines, consists of a set of two or more processing stages (or centers) with at least one stage having two or more parallel machines. The hybrid characteristic of a flow shop is ubiquitously found in various industries. The duplication of the number of machines in some stages can introduce additional flexibility, increase the overall capacities, and avoid bottlenecks if some operations are too long. So, scheduling in HFS has a great importance from both theoretical and practical points of view. Most scheduling problems are very difficult to solve (Blazewicz et al., 1996; Graham et al., 1979). That is why; the majority of the problems addressed in scheduling are only evaluated by a single criterion (such as makespan, total tardiness, workloads of machines, etc.) (T’kindt and Billaut, 2005). However, in the literature, many researches in scheduling show that the majority of industrial problems involve generally simultaneous incommensurable criteria, which they can sometimes be contradictory (Zitzler and Thiele, 1999). So, in this paper, we address a bi-criteria HFS scheduling problem which is the earliness–tardiness (ET) penalties (Hoogeveen, 2005). The ET problem encompasses a category of problem with the objective to complete each job as close to its due date possible. It represents a nonregular optimization criterion based on due dates (Gupta et al., 2002). The considered objective represents just in time (JIT) production concept (Portmann and Mouloua, 2007). In fact, in a JIT environment, minimizing earliness would reduce inventory costs and/or deterioration of product while minimizing tardiness would reduce a late cost or the loss of customers. In this scenario both early and tardy completion of jobs is disadvantageous to manufacturers and customers. This bi-criteria scheduling problem is NP-hard since the simpler mono-criterion HFS problem, made up of two stages and having at least two machines available in one of the stages, with makespan criterion is already NP-hard (Gupta, 1988). In addition, earliness/tardiness criteria, with distinct due dates, usually induce NP-hard problems (Hendel and Sourd, 2007). Then, it is unlikely to find an optimal solution without the use of an essentially enumerative algorithm and the computational time increases exponentially with problem size (Babayan and He, 2004). Therefore, the development of heuristics and meta-heuristics that can give good (or eventually optimal) solutions is well justified. So, this study considered the application of an ant colony optimization (ACO) meta-heuristic to HFS scheduling problem with minimization of the ET penalties. Indeed, ACO has been successfully used in solving several single criterion scheduling problems (see for example Alaykýran et al., 2007; Khalouli et al., 2008a). Likewise, some studies have recognized that the ACO approaches are suitable to solve multi-criteria scheduling problems such as in Gravel et al. (2002), Khalouli et al. (2008b), and Yagmahan and Yenisey (2008). The remainder of this paper is organized as follows. First, literature review section provides an overview related to the ET problems and the application of ACO method on scheduling. Section 3 is dedicated to the description of the HFS problem. Section 4 presents some constructive heuristics based on some priority rules for solving the considered problem. In Section 5, we describe the approach to solve the HFS problem with ET penalties. In order to show the efficiency of the suggested methodology, computational results are provided in Section 6. Finally, Section 7 concludes the paper.

The increase of competitiveness has motivated the implementation of JIT production on scheduling problem to reduce process inventories and delivering goods at time. In fact, this production environment is benefit to both manufacturers and customers. In this paper, we address the association of ET performance with the hybrid flow shop scheduling problem represents a practical production model used in real-life industries. The production goal is achieved by minimizing the early/tardy costs in order to complete each job as close to its due date. There are two essential issues to be dealt for multiple machine scheduling problems: job partition among machines and job sequence within each machine. So, we proposed an implementation of an ant colony optimization algorithm for this problem taking into account these latter issues and including some heuristics information that specifically take into account both earliness and tardiness penalties. To compare our proposed algorithm, we developed some constructive heuristics based on some dispatching rules used in the literature for flow shop scheduling problems. Some large randomly generated instances have been used to test the effectiveness of our approach. The results presented in this paper show that the proposed method outperforms the considered constructive heuristics and demonstrated that our proposed ACO-HFSET method can be a promising way for the considered scheduling problems. In this paper, we have considered the sum of the total earliness and tardiness costs. Practically tardiness is usually worst than earliness (Wu and Weng, 2005). Therefore, the utilization of different specifications of weight values to priority criteria can also be considered. Likewise, evaluation method can be used to select the best solution satisfying the preferences of the decision-maker based not only on the importance of each criterion but also on the interaction between the criteria by using an hybridization of our algorithm with some fuzzy logic techniques which could be an other directions for our works.