Research On Job Scheduling In Equipments Sharing Environment

Because demands for education resources had exceeded supplies in China,it was important to share education resources using information technologiesin public. As one of the core parts in the China Education Resources SharingSystem (CERS), the Equipments Sharing Application System involvedvaluable equipments in 211 project's universities which price are more than800,000 yuan. The system provided the powerful features such as equipmentsjoining, equipments appointing, experiments surrogation, job scheduling,training on line, etc. It made the process of equipments sharing transparent.Because most equipments in the sharing system were rare resources, it becameimportant that how to assign the little supplies to satisfy large demands. Wecalled it as the job scheduling problem in equipments sharing environment. The paper was arranged in following order:1. Modeling for job scheduling.The Equipments Sharing Application System encapsulated the static anddynamic information of equipments, and could provide the decision supportwhen a user was appointing equipments or a crew was scheduling jobs. Basedon the analysis of the equipments sharing process, we got the quantitativemodel of job scheduling. Furthermore, we discussed the uncertain factor in thesharing environment, and gave some response strategy.2. Research on optimal algorithm.The work studied the algorithms for the job scheduling problems in singleinterval and multiple intervals, including: ①Job Scheduling about FuzzyAppointments in Single Interval. It was equal to the 0-1 Single KnapsackProblem (NP problem). Based on the Dantzig algorithm, we worked out animproved heuristic algorithm, which could largely reduce scheduling error.②Job Scheduling about Exact Appointments in Single Interval. It was anpolynomial problem, and we proposed an algorithm based on dynamicprogramming, which time complexity was O(n*log n). ③Job Scheduling inMultiple Intervals. It was equal to the Multiple Knapsacks problem withAssignment Restricts (NP problem). To different actual application, weworked out the heuristic algorithm based on problem decomposition(HAPD), the branch-and-bound algorithm with little-branch first(BALF), the genetic algorithm based on interval encoding (GAIE).3. System design and implementation.The Equipments Sharing Application System was based on J2EE, weimplemented the system by following steps: requirements analysis,preliminary design, detailed design, coding. The key technical problemswere solved by perfect design patterns. The algorithms were implemented byC++, and encapsulated by Java Native Interface.