Scheduling Problems And Algorithm Research On Medical Examination

Many kinds of medical inspection process can be abstracted into open shop scheduling model,therefore,researching.For an open shop scheduling problem,each job can be processed by machines in any order.Each machine can process at most one job at one time and each job can be processed by at most one machine at one time.The processing procedure can't be interrupted until it is completed.The objective of open shop scheduling problem is to find a schedule minimizing one or some criterions.Open shop scheduling problems are widely applied to engineering technology and quality inspection and etc.Two kinds of criterions are considered in this paper,and branch&bound algorithm is designed to obtain the optimal solution for makespan problem,while differential evolution algorithm is applied to maximum lateness problem to obtain a near-optimal solution.Numerical simulation experiments are executed to demonstrate the effectiveness of these algorithms.The contents are summarized as follows:For minimizing makespan problem with release dates,branch&bound algorithms based on line coding and disjunctive graph model are designed.For the branch&bound algorithm based on line coding,branch strategy and lower bound and upper bound are presented.To demonstrate the effectiveness,the algorithm is compared with CPLEX of IBM by numerical simulation experiments.The branch strategy,lower bound and upper bound are presented for the branch&bound algorithm based on disjunctive graph model,and the feasibility of branch strategy is proved.The numerical simulation experiments comparing with CPLEX is executed too.This thesis researches the open shop scheduling problem to minimize the maximum lateness.For small and medium scale problem,the discrete differential evolution algorithm is designed.An improvement strategy is designed for this algorithm,then the numerical simulation experiments are executed.For large scale problem,DS-EDD heuristic algorithm is designed.The flow of the algorithm is presented and a lower bound is designed to compare with the heuristic algorithm.Then the performance of the algorithm is shown by numerical simulation experiments.