nternational Journal of Mechatronics, Electrical and Computer Technology Vol. 2(5), Oct, 2012, Special Number, pp 1026-1042, ISSN: 2305-0543 Available online at:
http://www.aeuso.org © Austrian E-Journals of Universal Scientific Organization
Meisam soleimani and Majid salimi* Information Technology Group – Mazandaran University Science &Technology *Corresponding Author's E-mail: [email protected]
Abstract
Scheduling in open shop problems is one of the most important scheduling problems in industries. Its solution area is huge, so it is among the hard problems. Then, using classic methods for optimal solution is of high time complexity and even impossible in some cases. Therefore, to solve these problems one is to use innovative methods. Among the articles on solving open shop problems, no one considered machine maintenance parameter; whereas, factories machinery will damage during operation due to various reasons which result in extensive loss such as, waste of time and extra cost for re-operating halfway procedure. Therefore, it is better to consider all things and control scheduling strictly. In this article, we proposed a new method to solve open shop scheduling problem using genetic algorithm that consider machinery maintenance for the best time.
Introduction
Regarding growing population of the world and increasing society demands for essential areas of life such as, food, clothing, housing, machinery, etc. there is an intense competition among the manufacturing companies aiming to produce in lower time and cost. Therefore, scheduling is important and many researchers had taken it into consideration. There are various kinds of scheduling in industry such as, Flow Shop, Job Shop, Open Shop, FMS, etc. Scheduling in Open shop systems is one of the important scheduling problems in industry that is complicated and involving huge solution area. There are m machines and n jobs in open shop scheduling problem; each job includes some operations. Each operation is to process by its corresponding machine and has a wide application in industry; for example, in repairing large airplanes which engine and electric systems repair is possible. These two operations are necessary (important) but it is impossible to perform them simultaneously.
Others include automobile repair, central quality control, appointment of class, inspection scheduling (technical examination), and satellite transmission that are described by Kubiak et al, Liu & Bulfin and Prins [1][2][3]. Up to now, several innovative methods had been developed which includes taboo search (TS) scheduling, ants’ colony (ACO) scheduling, genetic algorithm (GA), and Petri net. Genetic algorithm is one of the most using innovative methods. A lot had been done on open shop scheduling problems with genetic algorithm. OSSP aims to reach a possible combination of machine orders and specified job in which total time of make span is the shortest possible time. Several researchers had worked on solving open shop scheduling problem to reach more optimal time for problem solution. Followings are some of those researches on solving these problems. It should be noted that these researchers used different algorithms to solve the problems: Sahni and Gonzalez introduced an algorithm of O2||Cmax with a complexity of o (n) for two machines in an open shop problem [4]. Dorn dorf et al. used bound split and innovative algorithms to solve open shop scheduling problem [5]. They used split limiting method to avoid non-optimal solutions. In fact, they focused on other limitations and expanding methods to decrease search area. In addition, Tail lard suggested privacy issues on scheduling [6]. According matching algorithms (subsets of operations that can be processed and meanwhile will be combined with search radius during operations process in scheduling with small samples), Brasel et al[7]. Implemented various innovative and useful expanded algorithms. Gueret and Prins suggested other useful algorithms [8]. Among Metaheuristic algorithms, Alcaide solved Search Taboo algorithms with minimum make span for open shop problem [9]. Liaw suggested linking genetic algorithm with nearly minimum make span for open shop scheduling problem [10]. Linking algorithm is a combination of improved local routine based on Taboo Search in the basic genetic algorithm. Prins suggested other Genetic algorithms with very good results for standard problems [11]. In third section, open shop is described with an example and its scheduling Gantt chart. In fourth section, it is described about researchers’ works on this problem solving area. In fifth section, different steps of suggested algorithm are developed. In sixth section, you can see empirical results along with various charts and in the final section, we described conclusion.
2. Description
An open shop scheduling problem involves a collection of m machines and a collection of n jobs. Each job comprises of a collection of operations sometimes called tasks. Each machine can process at most one operation at a time and each job can be processed by at most one machine at any given time. Number of operations of each job equals number of machines and each operation is to process by its corresponding machine. Operation of each job is shown with Oij where i indicates job number and j indicates operation number that is to process by Mj machine. Each Oij contain a pre-identified Tij for processing by its machine without any interruption. Each machine processes maximum one operation at one time and each job is processed by one machine at one identified time. As a result, limitations of the problem are as follows:
1. Each operation has to be processed in its corresponding machine; 2. In each time, only one of the operations of each job is processed; 3. Each machine processes maximum one operation in any given time; 4. Each machine processes maximum one job in any given time; 5. The order in which the jobs are processed on the machine and the order in which the job is processed by the machine can be chosen arbitrary. Following is a solved example on OSSP: In the table, each job includes exactly one operation for each machine. These criteria are completely defined by a regular set of process times of m for each job. For example, table 1-1 shows a standard of 3*3 (3 jobs and 3 machines).
Table 1. Standard for 3 jobs and 3 machines
In the above example, operation 1 from job 1 is to process by machine 1 for 4 units of time and there is no limitation in job process. Problem is creating a valid solution with a minimum make span. The following figure shows Gantt chart of a scheduling for standard problem from table 1-1.
3. Suggested Algorithm
In this article, a new method of genetic algorithm is presented to solve open shop problem. This algorithm considers machine maintenance parameter. 3.1. Steps of Suggested Algorithm The following figure shows flowchart of suggested algorithm.
3.2. Chromosome
Presentation In the suggested algorithm for chromosome presentation, we used one-dimensional array which length equals with number of jobs’ operations meaning n*m. Each gene was as NMB where N, M, and B mean number of job, number of machine and machine maintenance field, respectively. If B = 1, this machine will move to a special rule (figure 4) the maintenance duration will be identified in which machine cannot complete its remaining operation. Figure 3 shows a sample chromosome where n = 3 and m = 3.
For example, in the chromosome shown in figure 2, fourth gene is 1,2,3 showing that second operation of third job will be processed by machine 2; and after process this machine will move to maintenance period and cannot process its new operation because its maintenance field is 1. Figure 4 shows Gantt diagram of chromosome shown in figure 3.
3.3. Description of Machine Maintenance Parameter
After processing some operations, each machine needs some maintenance time. During machine maintenance, that machine will be out of reach and after maintenance time it will be available again and can process operations. Figure 4 shows necessary maintenance time for machine based on machine age. Machine age equals total time of operations process done by it. Machine’s maximum age is A. If machine age reaches A, it will move to maintenance mode; and after each maintenance period, machine age will be zero.
3.4. Creating Initial Population
To create initial population, we produce n chromosomes randomly and use them for genetic algorithm and reproduction of next generation.
3.5. fitness
Fitness of a chromosome equals with necessary time of doing total operation. For example, in Gantt diagram of figure 5 scheduling fitness is 276. Following is coding for calculating the fitness of this problem.
Figure 4 shows scheduling of the sample chromosome in figure 3. The black section shows the duration of maintenance period for the corresponding machine. As you see, the machine does process no operation in the maintenance period.
3.6. Selection
Two-point random method is the selection operator in suggested algorithm. In this method, the initial population is divided into two sections and one chromosome is selected from each section randomly to exchange.
3.7. Crossover Operator
In this algorithm, we used two-point and reverse crossover operators. In two-point operator, two numbers is produced as genes index randomly after choosing two chromosomes as the parent. Then, the left genes of the first index in the first parent are accounted as the child and the related genes in second parent will be removed. Then, the right genes of the second parent are accounted as the parent and finally, the remained genes are accounted as child chromosome. In reverse crossover operator, one parent is chosen and reverse genes of parent chromosome produce the new child. Following figure shows the two-point crossover operator.
3.8. Mutation Operator
In mutation operator, after a chromosome selection, two genes are chosen randomly; then, these two genes are relocated with each other. B parameters of them are reversed during relocation, meaning that gene maintenance parameter 1 will be turned to 0 and vise versa.
3.9. Population Replacement
To choose the best children for next generations, initial population is sorting based on chromosomes fitness and then chromosomes of equal fitness are removed from the initial population as the number of exchange operator and mutation operator.
4. Empirical Results
We used C#.Net 2008 programming language to implement this algorithm. This program is executed on the computer with Core 2 Dou 2.2 GHz processer and 3GB Ram. We used 4 test data to compare algorithms. Calculations are done with the following parameters of genetic algorithm.
Figure 8 shows scatter chart of initial population meaning the number of produced chromosomes in each generation and different fitness for data test 1.
Conclusion
It is important to consider different aspects to create a proper scheduling. One of these aspects is considering maintenance parameter in industrial scheduling. In this algorithm, we suggested a new method to solve open shop scheduling problem considering machine maintenance parameter. The empirical results show that suggested algorithm is trying to reach the optimal solution through limiting searching in problem solving area and not considering chromosomes that does not influence the solution.
References
[1] K.W Sriskandarajah, C. Zaras, K. A Note on the Complexity of Open Shop Scheduling Problems, INFOR, Vol. 29, 284 - 294. [2] C.Y. Bulfin, R.L. Scheduling Ordered Open Shops, Comput. Oper. Res., Vol.14, 1987,257 - 264. [3] Prins, C.: An Overview of Scheduling Problems Arising in Satellite Communications, Journal. Oper. Res. Soc., Vol. 40, 1994, 611 - 623. [4] S. Gonzalez, T. Sahni, Open Shop Scheduling to Minimize Finish Time, J.Assoc.of ComputMach, Vol. 23, 1976, 665 - 679.
[5] U. Dorndorf, Pesch, E. Phan-Huy, T. Solving the Open Shop Scheduling Problem,Journal of Scheduling, Vol. 4, 2001, 157 - 174. [6] E. Taillard, Benchmarks for basic scheduling problems, European J. Oper. Res., Vol. 64, 1993,278 - 285. [7] H. Br¨asel, T. Tautenhahn, Werner, F. Constructive Heuristic Algorithms for the Open-Shop Problem, Computing, Vol. 51, 1993, 95 - 110. [8] C. Gueret, C. Prins, Classical and New Heuristics for the Open-Shop Problem: A Computational Evaluation, European J. Oper. Res., 107, 1998, 306 - 314. [9] D. Alcaide, J. Sicilia, D. Vigo, A Tabu Search Algorithm for the Open Shop Problem,Top, Vol. 5, 1997, 283 - 286. [10] C. F. Liaw, A Hybrid Genetic Algorithm for the Open Shop Scheduling Problem, EuropeanJ.Oper. Res., Vol.124, 2000, 28 - 42. [11] C. Prins, Competitive Genetic Algorithms for the Open-Shop Scheduling Problem, Math. Meth. Oper. Res., Vol. 52, 2000, 389 - 411
