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

Scheduling for the flexible job shop is very important in the fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem in medium and actual size problems with traditional optimization approaches owing to the high computational complexity. In this paper, dynamic scheduling in flexible job shop is considered. The dynamic status intensifies the complexity of this problem. Nevertheless, there are many industries which have a dynamic status. Two objectives are considered to make a balance between efficiency and stability of the schedules. A multi-objective mathematical model for the considered problem is developed. Since the problem is well known as NP-hard, a meta-heuristic algorithm based on the genetic algorithm is developed. Numerical experiments are used to evaluate the performance and efficiency of the proposed algorithm. The experimental results show that the proposed algorithm is capable to achieve the optimal solutions for the small size problems and near optimal solutions for the medium size problems.

Scheduling problems occur in all of the economic domains, from computer engineering to manufacturing techniques. Most scheduling problems are complex and combinatorial and so difficult to solve. The job shop scheduling is a branch of the production scheduling, which is well known as a combinatorial optimization problem. The job shop scheduling problem is to determine a schedule of jobs that have pre-specified operation sequences in a multi-machine environment. In the classical job shop scheduling problem (JSP), n jobs are processed for completion on m unrelated machines. For each job, technology constraints specify a complete, distinct routing which is fixed and known in advance. Each machine is continuously available from time zero, and operations are processed without preemption. The general JSP is strongly NP-hard [1]. Flexible job shop scheduling problem (FJSP) is an extension of the classical JSP which allows an operation to be processed by any machine from a given set. The scheduling problem of 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 [2]. The FJSP is a much more complex version of the JSP, so the FJSP is strongly NP-hard and combinatorial. It incorporates all of the difficulties and complexities of its predecessor JSP and is more complex because of the additional need to determine the assignment of operations to the machines [3] and [4]. Bruker and Schlie [5] were among the first to address flexible job shop scheduling problem. They developed a polynomial algorithm for solving the flexible job shop scheduling problem with two jobs. Lee et al. [6] presented a mathematical model for this scheduling problem and then improved a genetic algorithm to minimize the makespan time. Saidi-mehrabad and Fattahi [3] presented a mathematical model for solving the medium and large size problems of FJSP. They proposed a hierarchically approach algorithm based on a tabu search algorithm to solve this problem. Also this problem was solved by some other researchers (for example [7] and [8]). Because of unexpected events occurring in most of the real manufacturing systems, there is a new type of scheduling problem in most of industries named the dynamic scheduling problem. In dynamic scheduling problems, there is an infinite set of jobs that continue to arrive after the scheduling. In this situation, all jobs might not be available at first and might cause some disturbances during later scheduling. Some events that may occur in real manufacturing systems are machine failure, adding new machine (repairing or buying), new job arrival, job cancellation, changing processing time, rush order, rework or quality problem, due date changing, etc. [9]. In this paper, a multi-objective algorithm is developed for dynamic flexible job shop scheduling problem (DFJSP). Almost all of the literature published in this area, focuses on static FJSP or dynamic job shop scheduling problem (DJSP). The first study in dynamic job shop scheduling was published by Holloway and Nelson [10]. They implemented a multi-pass procedure by generating schedules periodically. They concluded that a periodic policy (scheduling/rescheduling periodically) is effective in dynamic job shop environments. Fang and Xi [9] provided a meta-heuristic method for the dynamic job shop scheduling problem. They presented a hybrid method based on the genetic algorithm and dispatching rules for solving job shop scheduling problems with sequence-dependent setup times and due date constraints. The results of their research show that their proposed strategy has a good performance in dynamic environment. Chryssolouris and Subramaniam [11] presented a genetic algorithm for DJSP. They considered two performance measures, named mean job tardiness and mean job cost, to demonstrate multiple criteria scheduling. They indicated that the genetic algorithms scheduling approach produced better scheduling performance in comparison with several common dispatching rules. Adibi et al. [12] presented a variable neighborhood search method for a multi-objective DJSP. They considered a JSP with random job arrivals and machine breakdowns. Their multi-objective performance measure consisted of two efficiency criteria (makespan and tardiness). The makespan criterion or efficiency criterion are considered by some other researches such as Liu et al. [13]. Clearly, improving efficiency is important in manufacturing systems that have dynamic job arrivals but the instability problem induced by unrestricted rescheduling renders the approach useless. Rangsaritratsamee et al. [14] indicated that the strategies applied in previous researches on DJSP can improve classic measures of efficiency. They presented a methodology to address DJSP based on a bi-criteria objective function that simultaneously considers efficiency and stability. Schedules are generated at each rescheduling point using a genetic local search algorithm that allows efficiency and stability to be balanced in a way that is appropriate for each situation. The dynamic models are seen, in abundance, in many other scheduling literatures such as, dynamic flexible assembly systems [15] and dynamic job shop production system with sequence-dependent setups [16]. This shows the important and practical usage of dynamic scheduling models in many industries. The goal of this research is to improve schedule efficiency and maintain stability through a methodology that uses a local search genetic algorithm and a multi-objective performance measure for DFJSP. So, the models presented by Rangsaritratsamee et al. [14] and Fattahi et al. [17] are developed in this paper to present an integrated model for DFJSP. The DFJSP is more practical than the DJSP in real shops. The DFJSP is more complex than the FJSP and the DFJSP therefore is strongly NP-hard. A heuristic approach to solve the DFJSP is presented based on a bi-criteria model that simultaneously considers the efficiency and stability criteria. A mathematical model is developed for DFJSP. The remaining sections of this paper are organized as follows: Section 2 describes the considered problem and presents a mathematical model. Section 3 develops a genetic algorithm for this problem. Experimental results are discussed in Section 4. Finally, Section 5 gives some concluding remarks and future research directions.

In this research, a mathematical model for the dynamic flexible job shop scheduling problem has been developed. Whereas this problem is well known as NP-hard, a meta-heuristic algorithm based on GA is developed. The proposed algorithm improves the efficiency and stability of schedules. Numerical experiments were used to evaluate the performance and effectiveness of the proposed algorithm. It is concluded that the bi-objectives model can improve the efficiency and stability of schedules based on a real example from a part making industry. The experimental results show that the proposed algorithm is capable of achieving the optimal solutions for the small size problems. Also the results of proposed algorithm are between the upper and lower bounds for the medium size problems. These upper and lower bounds of the optimal solutions are computed by the branch and bound method. So, the proposed algorithm is capable of reaching near optimal solutions for the medium size problems. The standard deviation of the solutions is equal zero for the small size problems which show the high quality of the algorithm on the small size problems. Nevertheless, the standard deviation of the solutions is increased for the medium and large size problems. So the convergence of the proposed algorithm is decreased for the large size problems. Also the genetic algorithm parameters are adjusted based on preliminary experiments. The proposed algorithm and mathematical model can be used in production environments and further research. Because of the multi-objective nature of the DFJSP, using a Pareto optimal method and other multi criteria decision making methods to this problem can be suggested for further research.