nternational Journal of Mechatronics , Electrical and Computer Technology Vol . ( ) Oct , Special Number , pp - , ISSN : - Available online at : 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 . 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 [ ] [ ] [ ]. 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 O || Cmax with a complexity of o ( n ) for two machines in an open shop problem [ ]. Dorn dorf et al . used bound split and innovative algorithms to solve open shop scheduling problem [ ]. 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 [ ]. 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 [ ]. Implemented various innovative and useful expanded algorithms . Gueret and Prins suggested other useful algorithms [ ]. Among Metaheuristic algorithms , Alcaide solved Search Taboo algorithms with minimum make span for open shop problem [ ]. Liaw suggested linking genetic algorithm with nearly minimum make span for open shop scheduling problem [ ]. 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 [ ]. 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 . 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 : . Each operation has to be processed in its corresponding machine ; . In each time , only one of the operations of each job is processed ; . Each machine processes maximum one operation in any given time ; . Each machine processes maximum one job in any given time ; . 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 - shows a standard of ( jobs and machines ) Table . Standard for jobs and machines In the above example , operation from job is to process by machine for 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 - . In this article , a new method of genetic algorithm is presented to solve open shop problem . This algorithm considers machine maintenance parameter . . . Steps of Suggested Algorithm The following figure shows flowchart of suggested algorithm . 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 = , this machine will move to a special rule ( figure ) the maintenance duration will be identified in which machine cannot complete its remaining operation . Figure shows a sample chromosome where n = and m = . For example , in the chromosome shown in figure , fourth gene is , showing that second operation of third job will be processed by machine ; and after process this machine will move to maintenance period and cannot process its new operation because its maintenance field is . Figure shows Gantt diagram of chromosome shown in figure . 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 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 . To create initial population , we produce n chromosomes randomly and use them for genetic algorithm and reproduction of next generation . Fitness of a chromosome equals with necessary time of doing total operation . For example , in Gantt diagram of figure scheduling fitness is . Following is coding for calculating the fitness of this problem . Figure shows scheduling of the sample chromosome in figure . 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 . 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 . 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 . 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 will be turned to and vise versa . 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 . We used C . Net programming language to implement this algorithm . This program is executed on the computer with Core Dou . GHz processer and GB Ram . We used test data to compare algorithms . Calculations are done with the following parameters of genetic algorithm . Figure shows scatter chart of initial population meaning the number of produced chromosomes in each generation and different fitness for data test . 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 .