Research On Concurrent Open-shop Scheduling Problem Based On Linear Relaxation

Concurrent open-shop scheduling problem can be considered as a relaxation type ofopen shop scheduling problem. Because of the wide application field and difficult problemsolving, it has been paid more attentions by researchers recently years. The properties ofconcurrent open shop is jobs have no precedence constrains. More than one machine canoperate one job at the same time. There’s interference machines constrains. The jobs havetime window constraints. It is not allowed to be interrupted and jobs have arrival time.The procedure of solving concurrent open shop scheduling problem is divided into twoprocedures, the exact solution and approximate algorithm solution. The exact solving givesthe exact solution of the problem and as a standard to evaluate the approximate algorithm’ssolution. With the scale of the problem growing, exact solving can’t give the problem’ssolution in finite time. Approximate algorithm can reduce the time waste on exact solution.It can give the approximate optimistic solution to the problem in a short time.The method of exact solution is to solve the buildiing problem’s mathematics integerprogramming. This paper uses two ways to build the concurrent open shop schedulingproblem’s mathematics integer programming. The solution of the integer programming isusing branch and bound algorithm combine with the software. Approximate algorithm isbased on the scheduling rules of integer programming relaxation. Relax the concurrent openshop scheduling problem’s integer programming of completion time variables. Reschedulethe jobs using the relaxation’s result. The solution of the minimize makespan and minimizethe sum of all jobs’ completion time which is the multi-objective function of the problemcan be getted.Finally, Using the application of civil aircraft ground support scheduling as an exampleto illustrate the concurrent open shop scheduling problem. The exact and approximatealgorithm can be used to solve the problem separately. The real civil aircraft ground supportscheduling problem can be solved by the algorithm.