Algorithms For Parallel Scheduling Of Multi Kinds Of Resources Under Eligibility Restrictions

This paper abstracts the model of parallel scheduling of multi kinds of essential resources under eligibility restrictions from the practical application background of task scheduling in a measurement and calibration laboratory.This model can be applied in other situations.For example,when an Internet finance service platform organizes united reviews which are performed by internal as well as outside experts to a large number of credti applications,the model may help to offer efficient algorithms to arrange the agenda reasonably.The model belongs to a kind of new-style scheduling problems.Former researches on scheduling problems under eligibility restrictions generally regard machines as the only kind of resource which is subjected to eligibility restrictions.Meanwhile,former research concentations are different machine eligibility restrictions,different hybrids of eligibility restrictions and other restrictions,and multi scheduling objectives.Up to current days,there is few document which lucubrates the parallel scheduling problem of multi kinds of essential resources under eligibility restrictions.Aiming at two cases where processing time of jobs is unit time as well as random time,this paper researches the new-style scheduling problems based on classical operation research methods and heuristic rule methods by applying innovative dynamic flexibility measurement,offers a series of optimal or heuristic algorithms with the objective of minimizing the timetable.In addition,the paper estimates and analyzes scheduling performance of the algorithms by means of large-scale numerical experiments.The achievements of this paper are as follows:Firstly,proposing original dynamic flexibility measurement method based on “processing opportunity” concept,which is more advantageous than the existing method in the case of uneven saturation degree of eligibility.Secondly,for the first time,clearly defining and expressing the problem of parallel scheduling with two kinds of essential resources under eligibility restrictions in the case of unit job processing time,establishing mathematical model of graph theory for it,and proposing an exact algorithm with better low complexity.In addition,two heuristic algorithms are given by using different dynamic flexibility measurement methods,which can achieve lower complexity and better scheduling effect.Thirdly,for the first time,clearly defining and expressing the problem of parallel scheduling with n(n?1)kinds of essential resources under eligibility restrictions in the case of unit job processing time,establishing a mathematical model of integer linear programming and giving an exact algorithm of polynomial time.Fourthly,for the first time,clearly defining and expressing the problem of parallel scheduling with two kinds of essential resources under eligibility restrictions in the case of random job processing time,proposing a framework of algorithm elements and some original strategies,giving a series of heuristic algorithms,identifying the "dominant algorithms" among them by numerical experiments,determining the existence conditions of these advantages and offering qualitative interpretation.