زمان بندی تولید کارگاهی انعطاف پذیر همراه با تداخل در عملیات

In this paper, flexible job shop scheduling problem with a new approach, overlapping in operations, is discussed. In many flexible job shops, a customer demand can be released more than one for each job, where demand determines the quantity of each finished job ordered by a customer. In these models each job has a demand more than one. This assumption is an important and practical issue for many flexible job shops such as petrochemical industries. To consider this assumption, we use a new approach, named overlapping in operations. In this approach, embedded operations of each job can be performed due to overlap considerations in which each operation may be overlapped with the others because of its nature. The overlapping is limited by structural constraints, such as the dimensions of the box to be packed or the capacity of the container used to move the pieces from one machine to the next. Since this problem is well known as NP-Hard class, a hierarchical approach used simulated annealing algorithm is developed to solve large problem instances. Moreover, a mixed integer linear programming (MILP) method is presented. To evaluate the validity of the proposed SA algorithm, the results are compared with the optimal solution obtained with the traditional optimization technique (The Branch and Bound method). The computational results validate the efficiency and effectiveness of the proposed algorithm. Also the computational results show that the overlapping considering can improve the makespan and machines utilization measures. So the proposed algorithm can be applied easily in real factory conditions and for the large size problems and it should thus be useful to both practitioners and researchers.

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 to completion on m unrelated machines. For each job, technology constraints specify a complete, distinct routing which is fixed and known in advance. Processing times are 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]. In order to match nowadays market requirements, manufacturing systems have to become more flexible and efficient. To achieve these objectives, the systems need not only the automated and flexible machines, but also the flexible scheduling systems. The flexible job shop scheduling problem (FJSP) extends JSP by assuming that, for each given operation, there is at least one instance of the machine type necessary to perform it. 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 [2]. The FJSP is strongly NP-hard and combinatorial [2] and [3]. In many flexible job shops, a customer demand can be released more than one for each job, where demand determines the quantity of each finished job ordered by a customer. A demand more than one for each job is a new assumption in the flexible job shop scheduling problems which is discussed in this paper. This assumption is an important and practical issue for many flexible job shops such as petrochemical industries and glass factory (see, for example, [4]). To consider this assumption in the flexible job shop scheduling problem, we use a new approach, named overlapping in operations. In each job, embedded operations can be performed due to overlap considerations in which each operation may be overlapped with the others because of its nature. The overlapping is limited by structural constraints, such as the dimensions of the box to be packed or the capacity of the container used to move the pieces from one machine to the next. To more explanation of the overlapping approach, let us consider an example of a flexible job shop with two jobs and three machines which is presented in Fig. 1. In this problem, Job1 has two operations (namely o1,1, o1,2) and Job2 has three operations (namely o2,1, o2,2, o2,3). Job1 must produce 20 product of A and job 2 must produce 10 products of B. Assume that the operation o2,1 use the machine m3, the operation o2,2 use the machine m1 and the operation o2,3 use the machine m2. In this situation, we do not have to wait until all the o2,1 operations have been done to start the o2,2 operations. Fig. 2 shows an illustration of the overlapping in the operations of job1. As shown in this figure, operations o2,1, o2,2 and o2,3 are overlapped. Sometimes this overlapping is automatic, that is, as soon as the first piece has been processed on a machine, it goes directly to the next machine. Full-size image (16 K) Fig. 1. Example of two jobs-three machines scheduling problem. Figure options Full-size image (20 K) Fig. 2. An illustration of overlapping in operations. Figure options The FJSP with overlapping in operations is a much more complex version of the FJSP, so the FJSP with overlapping in operations is strongly NP-hard and combinatorial. It incorporates all of the difficulties and complexities of FJSP and is more complex than FJSP because of the addition limitations such as dimensions of the box to be packed or the capacity of the container and the customer demand can be released more than one. The literature of FJSP is considerably sparser than the literature of JSP. Bruker and Schile [5] were among the first to address this problem. They developed 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. In the 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-problem can be separated. Brandimarte [6] was the first in applying this decomposition approach 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 tabu search heuristic [2]. Saidi and Fattahi [7] presented a mathematical model and a tabu search algorithm to solve the flexible job shop scheduling problem with sequence-dependent setups. They used a hierarchical approach with two heuristic to solve this problem. The first one for assigning each operation to a machine out of a set of capable machines and the second one for sequencing the assigned operations on all machines in order to obtain a feasible schedule minimizing the Makespan. Another work in this field was represented by Kacem et al. [8] and Xia and Wu [2]. Integrated approaches were used by considering assignment scheduling at the same time. Hurink et al. [9] proposed a tabu search heuristic in which reassignment and rescheduling are considered as two different types of moves. The integrated approach which had been represented by Dauzere-Peres and Paulli [10] was defined a neighborhood structure for the problem where there was no distinction between reassigning and resequencing an operation. Mastrololli and Gambardella [11] improved Dauzere-Peres tabu search techniques and presented two neighborhood functions. This paper considers flexible jobs scheduling problem with overlapping in operations. Since the problem is well known as NP-Hard class, a simulated annealing algorithm is developed to solve large scale problems. Moreover, a mixed integer linear programming (MILP) method is presented to validate the proposed algorithm. The approach is tested on a set of random generated test problems to evaluate the behaviour of the proposed algorithm. The reminder of this paper is organized as follows: Section 2 describes the problem under consideration and presents a mixed integer linear programming model. The solution procedure and hierarchical approach are presented in Section 3. Section 4 presents numerical experiments and discussion. Section 5 includes concluding remarks.

In this paper, flexible job shop scheduling problem with a new approach, overlapping in operations, is discussed. In many flexible job shops, a customer demand can be released more than one for each job, where demand determines the quantity of each finished job ordered by a customer. Considering a demand more than one for each job is a new assumption in flexible job shop scheduling problems which is discussed in this paper. This assumption is an important and practical problem for many flexible job shops such as petrochemical industries. To consider this assumption in flexible job shop scheduling problem, we presented a new approach, named overlapping in operations. Since this problem is well known as NP-Hard class, a hierarchical approach which uses simulated annealing heuristic is developed to solve large problem instances. Moreover, a mixed integer linear programming (MILP) method is presented to validate the proposed algorithm. The proposed hybrid algorithm implemented using the Visual Fortran. Computational results show that the proposed algorithm can find good quality solution for the flexible job shop scheduling problem with overlapping in operations in a small time. The computational results validate the efficiency and effectiveness of the proposed algorithm. Also the computational results show that the overlapping approach can improve the makespan and machines utilization measures. The proposed algorithm can be applied easily in real factory conditions and for large size problems. It should thus be useful to both practitioners and researchers. Although the mathematical model and the hybrid algorithm are presented in the context of makespan minimization, they can be easily adapted for other single objective optimization problems such as minimization of total weighted tardiness. To better evaluation of these problems we can use the multi objective optimization techniques. So use the multi objective optimization technique to improve the approach can be suggested for further research.