Research On Multi-installments Scheduling Algorithm And Its Application In Image Processing

When distributed systems store images,some backups will be placed in multiple processors in case of data loss.However,when the images need to be transmitted and computed,conventional scheduling strategy prefers single-installment scheduling.Although single-installment scheduling is marked by simple and easy to solve,while it fails to make full use of the distributed systems since some processors require a long wait before starting the task.Fortunately,multi-installment scheduling can solve this problem.In view of this,this paper employs multi-installment scheduling to optimize image processing in distributed systems,and therefore establishes multi-installment scheduling models with the minimum makespan as the optimization objective,then studies the related problems of both homogeneous and heterogeneous distributed systems respectively.The main research results are as follows:1.For homogeneous distributed systems,different existing multi-installment scheduling model,which firstly transfers data and then carries out distributed computing,a novel multi-installment scheduling is proposed.The proposed model is more in line with the characteristics of distributed systems as it let processors to process data before the results retrieval.The model involves two sets of variables: task allocation scheme and number of installments.To obtain the solution,firstly,the constraint relationship among processors in each installment is analyzed,and then the closed-form solution of optimal task allocation scheme is derived.Secondly,the closed-form solution of the optimal number of installments is derived by rigorous mathematical proof.Finally,experiments show that the multi-instalment scheduling model can minimize the makespan.2.For heterogeneous distributed systems,taking the shortest makespan as the optimization objective,a multi-installment scheduling model is proposed.The model involves three sets of variables: processors sequence,task allocation scheme and number of installments.Firstly,the closed-form solution of the optimal task allocation scheme is obtained by formula derivation under the condition of given processor sequence and installments.Secondly,under the condition of given processor sequence,the closed-form solution of the optimal number of installments is derived,and the correctness of the solution procedure is proved.Then,an effective evolutionary algorithm is designed to solve the optimal processor sequence.Finally,simulation results show that the proposed algorithm can obtain the optimal processor scheduling sequence and the shortest makespan.In addition,by analyzing the experimental results,it is found that the descending sequence of communication speed can be regarded as the approximate optimal processor sequence.3.To verify the effectiveness of the proposed model and algorithm,this paper conducts multi-installment scheduling experiments on the image compression problem,and the image is released by NASA.Firstly,according to the proposed model and algorithm,the optimal processor sequence,number of scheduling installments and optimal task allocation scheme are obtained.And then,the scheduling is executed on the distributed systems,meanwhile the implementation of each processor is monitored and recorded.Finally,the experimental results indicate that the proposed both model and algorithm are effective.