Research On Flexible Open Shop Scheduling Algorithm

Scheduling is the core content and key technology in production managerment. Proper and effective scheduling can help minimize makespan, waste of resources, and increase economic benefit. With the upgrading of market competition and complexity of production process, scheduling is playing an increasingly important role in the manufacturing industry.Flexible open shop scheduling problem (FOSSP) is one of the most well-known scheduling problems. Meanwhile, FOSSP is one of the most difficult combinatorial optimization problems. Mathematical modeling and approximation algorithms for FOSSP with preemptive constraint, non-preemptive constraint and machine availability constraint (Om(P)|pmtn,r1|Cmax,Om(P)||Cmax and Om(P)|r, aN.I|Cmax) were studied systemly in this thesis. Three approximation algorithms for the three FOSSP problems were proposed, which were based on network flow and semi-matching theory. And the performance parameters of the three algorithms were analysised, such as worse-case ratio and time complexityThe main contents are as following:1. Mathematical modeling methods of FOSSP were studied. Constraint conditions of Om(P)|pmtn, ri|Cmax,Om(P)||Cmax and Om(P)|r,aN.1|Cmax problems were analysis, which were represented by constraint functions. Then three mixed integer programming models with the objective of minimizing the makespan for Om(P)|pmtn, ri|Cmax,Om(P)||Cmax and Om(P)|r,aN |Cmax problems were established, which set a foundation for scheduling algorithm verification.2. A network flow based algorithm for Om(P)|pmtn, ri|Cmax problem was presented, which decomposed Om(P)|pmtn,ri|Cmax, problem into resource allocation and job sequencing two sub-problems. Firstly, the maximum flow model was developed to model the resource allocation and time constraints. and the maximum flow was the solution of the resource allocation, which made machine in full load condition. Moreover a new pre-flow push algorithm and optimization method for the maximum flow model were putforward, which used the least load first rule and the largest task first rule in active node selection. Based on the solution of machine allocation problem got by pre-flow push algorithm, the sequences of the tasks processed by each machine were determined by calculating the matrix of the processing times and decrementing set.3. Due to the complexity of Om(P)||Cmax problem, a dense scheduling algorithm was developed, which decomposed Om(P)||Cmax problem into resource matching and optimization two sub-problems. Only one operation of each job was completed in each resource matching, so m times of resource matching should be done for jobs set containing m operations. Initial solution was got by connecting resource matching results. Resource matching was modeled by a semi-matching on weighted bipartite graph, and two semi-matching algorithms were developed. For small scale scheduling problem, a balanced semi-matching algorithm based on augmenting path was presented, and a balanced semi-matching algorithm genetic algorithm was developed for large scale scheduling problem. Meanwhile, initial solution and scheduling optimization method was presented.4. The lower bound on makespan in Om(P)|r, aN.1|Cmax problem was studied. By relaxing the non-preemptive constraint, Om(P)|r, aN.1|Cmax problem can be converted into Om(P)|r, aN.1, pmtn |Cmax problem that can be solved easier, and the makespan of Om(P)|r, aN.1, pmtn|C problem can be served as the lower bound on makespan in Om(P)|r, aN.1|Cmax problem. The concrete procedure was that, firstly, the mixed integer programming model with the objective of minimizing the makespan for Om(P)|r, aN. 1,pmtn\Cmax problems was established, which was used as foundation to develope the maximum flow model for Om(P)|r, aN 1, pmtn|C, problem. Then, the makespan of Om(P)|r, aN.1, pmtn|Cmax problem can be got by maximum flow algorithm, which were the lower bound on makespan in Om(P)|r, aN. 1|Cmax problem.5. We developed a dense scheduling algorithm for Om(P)|r. aN.1|Cmax problem with a worst-case performance ratio less than 2. In Om(P)|r, aN.1|Cmax problem, each machine has a fixed and known unavailable period, and job interrupted by unavailable period can continue to be processed on the same machine after the machine has become available. In this thesis, the unavailable periods were treated as special jobs, which were called virtual jobs. In order to reduce the difficulty, resource matchings were done firstly without consideration of virtual job. Then, the relationship between makespan of resource matching and virtual job was analysis, and three modes were got. The method Based on the analysis, a dense algorithm for Om(P)|r, aN.1|Cmax problem were developed.The performances of the three algorithms developed in this paper were analysis from two aspects:firstly, worse case ratio and time complexity were analysis; then, the validity of the developed scheduling algorithms were illustrated by randomly generated examples.