موجودی بر اساس مدل برنامه ریزی دو هدفه ی کار فروشگاه و الگوریتم ژنتیک ترکیبی آن

Job shop scheduling problem is a typical NP-hard problem. An inventory based two-objective job shop scheduling model was proposed in this paper, in which both the make-span (the total completion time) and the inventory capacity were as objectives and were optimized simultaneously. To solve the proposed model more effectively, some tailor made genetic operators were designed by making full use of the characteristics of the problem. Concretely, a new crossover operator based on the critical path was specifically designed. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm.

The job shop scheduling problem (JSSP) is one of the most well-known scheduling problems with strong engineering backgrounds and has been proved to be NP-hard [1]. Since the benchmarks of JSSP were presented by Fisher and Thompson in 1963 [2], the single objective JSSPs have attracted wide research attention. Most studies of single objective JSSPs result in a schedule to minimize the time required to complete all jobs, i.e., to minimize the makespan. Historically, JSSP has been primarily treated by exact methods [3], such as branch and bound, linear programming and Lagrangian relaxation. Over the past two decades, meta-heuristics have gained wide research attention [4], [5] and [6], including such topics as the shifting bottleneck approach, particle swarm optimization, simulated annealing, Tabu search and genetic algorithm. However, in many real-life scheduling problems, the decision makers are frequently faced with situations in which the appropriateness of a schedule is measured against multiple objectives. This means the final schedule must consider various objectives simultaneously. Consequently, scheduling falls into the category of multi-objective optimization problems. So far, few researchers have attempted to tackle the multi-objective JSSPs (MJSSPs). The importance of multi-criterion scheduling problems and some techniques to find solutions were briefly summarized in Nagar et al. [7]. Sakawa and Kubota [8] presented a genetic algorithm incorporating the concept of similarity among individuals. The objectives were to maximize the weighted sum of the minimum agreement index, the average agreement index and the maximum fuzzy completion time. Ponnambalam et al. [9] proposed a multi-objective genetic algorithm and the objectives were to minimize the weighted sum of makespan, the total idle time of machines and the total tardiness. Esquivel et al. [10] proposed an enhanced evolutionary algorithm with new multi-re-combinative operators and incest prevention strategies for single and multi-objective job shop scheduling problem. Low et al. [11] proposed a mathematical model for MOJSSP to minimize the total job flow time, total job tardiness, and machine idle time. Lei and Wu [12] developed a crowding measure-based multi-objective evolutionary algorithm for the problems of job shop scheduling to minimize the makespan and the total tardiness of jobs. A Pareto archived simulated annealing method was developed by Suresh and Mohanasndaram [13] to find non-dominated solution sets for the MOJSSP with the objectives of minimizing the makespan and the mean flow time of jobs. Ripon et al. [14] presented a jumping genes genetic algorithm by imitating a jumping gene phenomenon to solve MOJSSP. Petrovic et al. [15] used GA with a linguistically quantified decision function for solving a MOJSSP. Lei [16] presented a particle swarm optimization for the MOJSSP to minimize makespan and total job tardiness simultaneously. Qian et al. [17] proposed a memetic algorithm based on differential evolution for MOJSSP. Kachitvichyanukul and Sitthitham [18] presented a two-stage genetic algorithm (2S-GA) for MOJSSP. The 2S-GA was proposed with three criteria: minimizing makespan, minimizing total weighted earliness, and minimizing total weighted tardiness. Sha and Lin [19] constructed a particle swarm optimization for an elaborate MOJSSP and modified the particle position representation, particle movement, and particle velocity. Vázquez-Rodríguez and Petrovic [20] proposed a new hybrid dispatching rule based genetic algorithms. Tavakkoli-Moghaddam et al. [21] presented a combination of particle swarm optimization and genetic operators for MOJSSP that minimizes the mean weighted completion time and the sum of the weighted tardiness/earliness costs. Huang [22] focused on lot splitting in the job-shop scheduling problem and attempted to minimize the weighted total of stock, machine idle and carrying costs. Adibi et al. [23] applied a multi-objective performance measure to the MOJJSP as objective function that consists of makespan and tardiness. Moslehi and Mahnam [24] present a new approach based on a hybridization of the particle swarm and local search algorithm to solve the multi-objective flexible job-shop scheduling problem. Fang et al. [25] proposed an optimization method of many goals scheduling based on grey relation theory and ant colony algorithm for the MOJJSP. Previous literature indicates that the completion time, tardiness, flow time, lateness, earliness and the number of tardy jobs are often used as the optimization criteria in MOJSSP. These objectives are constructed based on the completion situation of the jobs and are hardly taken the inventory capacity into account. So in this paper, we considered both the completion situation of the jobs and the inventory capacity in the objectives, constructed an inventory based MOJJSP model. In order to solve the proposed MOJJSP model more effectively, some genetic operators was designed. Based on these genetic operators, we proposed a hybrid genetic algorithm (HGA). Finally, the efficiency of the proposed algorithm was verified by computer simulations on some typical scheduling problems. The remainder of the paper is organized as follows. We first introduce the concepts of multi-objective problems in Section 2. Then, we describe the problem considered and its mathematical model in Section 3. In Section 4, a hybrid genetic algorithm to the MOJSSP is presented. Section 5 presents the experimental results. The conclusions are made in Section 6.

We considered both the completion time of the jobs and the inventory capacity as the objectives, and constructed an inventory based MOJJSP model in this paper. To solve the proposed model, a new crossover operator based on the critical path was designed. A local search operator was designed in order to improve the quality of the solutions. Based on these, a hybrid genetic algorithm was proposed. The experimental results show that the proposed algorithm is effective and performs better than the compared algorithm.