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

The introduction of robotic cells to manufacturing systems improved the efficiency, productivity and reliability of the system. The main objective of the scheduling problem of multi-item multi-machine robotic cells is the identification of the optimum robot cycle/s and jobs sequencing for certain processing conditions which yield the higher possible production rate. The objective of this work is to solve the scheduling problem in four-machine blocking robotic cells producing identical and different part types while minimizing the cycle time. A genetic algorithm is developed to find the parts sequence that minimizes the robot-moves cycle time for each robot cycle. The results showed that the developed genetic algorithm yields competitive results compared to the results of the full enumeration of all possible parts sequences. The results show also that the ratio between the average processing time of all parts and the robot travel time determines the cycle having the optimal robot-moves.

In robotic cells, the robot performs a sequence of actions during which k parts are produced. This sequence of robot actions is defined by Sethi et al. [1] as k-unit cycle. A special case of the k-unit cycle is the one unit cycle in which only one part enters the cell and only one part leaves it while each machine is loaded and unloaded only once. He showed that the number of all possible robot-moves cycles for one unit cycle robotic cell is “m!” where m is the number of machines in the cell. For cells producing identical parts from two up to “m” machines were studied for scheduling of robot moves that minimize the robot cycle time. In case of cells producing different part types, the problem was solved for m machines and sequencing of parts such as to minimize the makespan [2] and [3]. Sethi et al. [1] proved that for two machines cell, the optimal one unit cycle is superior to any k-unit cycle and they conjectured this to be true for “m ⩾ 3”. Hall et al. [4] proved that for three machines cells producing identical parts, the optimum one unit cycle dominates all two unit cycles. Brauner and Finke [5] confirmed that Sethi et al. [1] conjecture is valid for two and three machines cell. For four machines the one unit cycle dominates the two unit cycle in cells with equidistance machines, and the three-unit cycles dominate all one unit cycles [5]. Most of the research work in the field of scheduling of robotic cells focused on the study of cells with identical parts [6], [7] and [8]. Other researches considered different part types and few considered Minimal Part Set (MPS) (which is the fixed ratio between the numbers of produced parts every cycle) [2], [3], [5], [9] and [10]. In case of scheduling different parts in a robotic cell, a focus is made on special category of robot move sequences which is called Concatenated Robot Move sequences (CRM). The CRM is achieved by repeating one unit cycle ‘n’ times to produce ‘k’ parts [11]. Most studies fix the robot move sequences to be a CRM sequence and then find the MPS part schedule that minimizes the total cycle time. The best part schedules for each CRM sequence are then compared [12]. The robot-move cycles can be classified according to the difficulty of cycle time calculations. The first class includes cycles which are trivially solvable in which their cycle time can be calculated by derived equations. The second class includes other cycles which are either solvable in polynomial time or non-polynomial time. The third class concerns cycles which depend on job sequences, where cycle times cannot be calculated using equations or exact formulation. These cycles are considered to be NP-hard and require heuristics for cycle time calculations as stated by Kamoun et al. [10]. The methods used to solve the robotic cell problem varied between heuristics, CPM–PERT, linear programming, integer programming, dynamic programming, branch and bound, deriving upper and lower bounds while most researchers solved the problem by formulating it as a Traveling Salesman Problem (TSP). Genetic Algorithm (GA) was used to overcome the complexity of solving large scale problems and NP hard cycles [2] and [3]. Carlier et al. [2] investigated the problem of “m” machines robotic cell with a blocking constraint. They proposed a number of heuristics to minimize the makespan namely; the approximate decomposition algorithm, the exact branch-and-bound algorithm and the genetic algorithm. They reported that the proposed optimization-based approaches deliver high-quality solutions. The genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times. Genetic algorithm was also used by Soukhal and Martineau [3] for solving large scale problems minimizing the makespan for m machines cells and gave good results. NP hard cycles were studied by few researchers due to its complexity. NP-hard cycles may result in minimum cycle times when compared to other cycles. Sadek et al. [9] used mathematical simulation to solve the NP hard cycles. In the three machines robotic cells there were two NP hard cycles out of all the six cycles. The two NP hard cycles were proved to be optimal. Limited work tackled the scheduling problem in four machine cells [9] and [13]. The problem of scheduling robot moves and sequencing parts simultaneously in cells that produce different part types and contain more than three machines was tackled by Kamoun et al. [10]. They solved the MPS sequencing under different robot moves cycles in three machines robotic cells. They also gave a methodology for extending this heuristic to four machines cells. Due to the difficulty of finding the optimal solutions to the problem of four machines cells; they found a lower bound and tested the heuristic against it. Kamoun et al. [10]. concluded that when the robot is relatively slow, the cycle in which the loading of machines is done in regular sequence (1, 2, …, m) is probably the optimal cycle since it has the minimum travel time. While the cycle in which the loading is done in reversed sequence (m, m – 1, …, 1) might be the optimal cycle when the robot is relatively fast because it allows each machine as much time for processing as possible. It was recommended that cycle #1 is the optimum robot cycle and superior to other cycles for low ratios between processing time and robot travel time while cycle #24 become the optimum cycle for higher ratios between processing times and robot travel times. The in-between cycles must be explored as they may lead to better solutions than cycles #1 and 24. The objective of this work is to solve the scheduling problem in four-machine blocking robotic cells producing identical and different parts while minimizing the cycle time. The problem includes scheduling of robot moves and sequencing of parts simultaneously. A genetic algorithm is developed to solve the problem. The solution is based on finding a parts’ sequence for each robot move cycle. The sequence with minimum cycle time is considered the best reached one. The performance of the genetic algorithm is measured by comparing the results with the results of full enumeration of all possible parts sequences. The cycle times of the enumerated sequences is calculated for the 24 robot moves cycles. Mathematical simulation is used to track the robot actions and used in calculating the cycle time. The rest of this paper is organized as follows: Section 2 presents the problem assumptions and configuration. In Section 3, the algorithm is tested against the full enumeration technique. Finally, Section 4 concludes the main results.

A genetic algorithm was developed and used to solve the problem of scheduling robot moves and jobs sequencing in four-machines blocking robotic cells producing identical or different jobs to minimize the cycle time. The developed GA was tested against the full enumeration procedure and showed high performance in solving the problem. Enumeration was efficient only in scheduling small size problems incorporating a limited number of jobs in a four machine robotic cell. As the number of jobs increases, enumeration fails to reach a solution. On the other hand, GA proved to be efficient in solving problems with large number of parts in considerably short time, whether the problems are unconstrained or constrained (MPS) and with identical or non-identical parts in four machines robotic cells. The ratio between the mean processing time and robot travel time plays major role in determining which robot cycle has the minimum cycle time. In general, cycle #24 gives the minimum cycle time for values of (tp/tt) higher than 5 which agree with previous research in the field. Although cycle #9 yielded optimal cycle time in the same range of (tp/tt), cycle #24 is most dominant. For lower values of (tp/tt), other cycles show better cycle times. Among these cycles are cycles number 11, 19, 13, and 21. It was shown that cycle #21 is superior to other cycles for (tp/tt) in the range between 1.02 and 5. Cycle #1 is the optimum robot cycle and superior to other cycles for low ratios of (tp/tt) lower than 0.95. The cycle/s that yields the optimum robot cycle time are independent of the number of jobs being processed. Although more than one cycle may give the minimum robot cycle time, the best cycle is determined based on the robot utilization, the smaller the utilization the better the cycle. Also robot utilization determines the optimum robot cycle(s) when all cycles are process dominant.