یک روش بهینه سازی ترکیبی موثر برای مشکلات برنامه ریزی تولید کارگاهی انعطاف پذیر چند هدفه

Scheduling for the flexible job-shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches owing to the high computational complexity. The combining of several optimization criteria induces additional complexity and new problems. Particle swarm optimization is an evolutionary computation technique mimicking the behavior of flying birds and their means of information exchange. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) as a local search algorithm employs certain probability to avoid becoming trapped in a local optimum and has been proved to be effective for a variety of situations, including scheduling and sequencing. By reasonably hybridizing these two methodologies, we develop an easily implemented hybrid approach for the multi-objective flexible job-shop scheduling problem (FJSP). The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the multi-objective FJSP, especially for problems on a large scale.

Scheduling problems occur in all the economic domains, from computer engineering to manufacturing techniques. Most scheduling problems are complex combinatorial optimization problems and very difficult to solve. The job-shop scheduling problem (JSP) is a branch of production scheduling, which is among the hardest combinatorial optimization problems. The classical JSP consists in scheduling a set of jobs on a set of machines with the objective to minimize a certain criterion, subject to the constraint that each job has a specified processing order through all machines which are fixed and known in advance. It is well known that this problem is NP-hard (Garey, Johnson, & Sethi, 1976). That means with current algorithms even moderately sized problems cannot be solved to guaranteed optimality. Many different approaches have been applied to JSP. Although an optimal solution algorithm for the classical JSP has not been developed, there is a trend in the research domain to solve a much more complex version of the problem. The problem is referred to as the flexible job-shop scheduling problem (FJSP). FJSP is an extension of the classical JSP which allows an operation to be processed by any machine from a given set. It incorporates all of the difficulties and complexities of its predecessor JSP and is more complex than JSP because of the addition need to determine the assignment of operations to machines. The scheduling problem of a FJSP consists of a routing sub-problem, that is, assigning each operation to a machine out of a set of capable machines and the scheduling sub-problem, which consists of sequencing the assigned operations on all machines in order to obtain a feasible schedule minimizing a predefined objective function. The FJSP mainly presents two difficulties. The first one is to assign each operation to a machine, and the second one is to schedule these operations in order to make a predefined objective minimal. The literature of FJSP is considerably sparser than the literature of JSP. Bruker and Schlie (1990) were among the first to address this problem. They develop a polynomial algorithm for solving the flexible job-shop problem with two jobs. For solving the realistic case with more than two jobs, two types of approaches have been used: hierarchical approaches and integrated approaches. In hierarchical approaches assignment of operations to machines and the sequencing of operations on the resources or machines are treated separately, i.e. assignment and sequencing are considered independently, whereas in integrated approaches, assignment and sequencing are not differentiated. Hierarchical approaches are based on the idea of decomposing the original problem in order to reduce its complexity. This type of approach is natural for FJSP since the routing and the scheduling sub-problems can be separated. Brandimarte (1993) was the first to use this decomposition for the FJSP. He solved the routing sub-problem using some existing dispatching rules and then focused on the scheduling sub-problem, which is solved using a taboo search heuristic. Tung, Li, and Nagi (1999) developed a similar approach for scheduling a flexible manufacturing system. Recently, Kacem et al., 2002a and Kacem et al., 2002b proposed a genetic algorithm controlled by the assigned model which is generated by the approach of localization (AL). And they used it to mono-objective and multi-objective FJSP. Integrated approaches were used by considering assignment and scheduling at the same time. Hurink, Jurisch, and Thole (1994) proposed a taboo search heuristic in which reassignment and rescheduling are considered as two different types of moves. The integrated approach which had been presented by Dauzere-Peres and Paulli (1997) was defined a neighborhood structure for the problem where there is no distinction between reassigning and resequencing an operation. A taboo search procedure is proposed based on the neighborhood structure. Mastrolilli and Gambardella (2002) improved Dauzere-Peres' taboo search techniques and presented two neighborhood functions. Most researchers were interested in applying taboo search techniques and genetic algorithms to FJSP in the past. In this research paper a practical hierarchical solution approach is proposed for solving multi-objective FJSP. The proposed approach makes use of particle swarm optimization (PSO) to assign operations on machines and simulated annealing (SA) algorithm to schedule operations on each machine. The considered objective is to minimize makespan (maximal completion time), the total workload of machines, and the workload of the critical machine. The remainder of the paper is organized as follows: the notation and problem description are introduced in Section 2. Section 3 describes standard PSO algorithm and how to apply it to multi-objective FJSP. Section 4 focuses on basic ingredients of SA, introducing some rules of parameters selection. The hybrid optimization algorithm is described in Section 5. In Section 6, computational experiments performed with the new hybrid optimization approach for three representative instances of FJSP are reported followed by the comparison to other heuristic methods. Some concluding remarks are made in Section 7.

We have discussed a new approach based on the hybridization of PSO and SA for solving multi-objective flexible job-shop scheduling problems. Although it does not guarantee the optimality, such an approach provides solutions with good quality in a reasonable time limit. The performance of the new approach is evaluated in comparison with the results obtained from other authors' algorithms for three representative instances. The obtained results show the effectiveness of the proposed approach. Although there is a huge amount of literature on classical JSP, the FJSP does not have a rich literature. Therefore, there is still a need to develop effective approach for this complex problem. The proposed hybrid approach in this paper can be considered as effective mechanisms from this point of view. There are a number of research directions that can be considered as useful extensions of this research. Although the proposed algorithm is tested with three representative instances, a more comprehensive computational study should be made to test the efficiency of proposed solution technique. Research on generalization of such an approach for solving other multi-objective optimization problems should be an interesting subject. Furthermore, applying PSO to other combinatorial optimization problems is also possible in further research.