Duration automation in scheduling program for a cluster computer system

Abstract

Optimal schedule for works running on machines, in a general case, is a hard problem and there is no complete optimal deterministic algorithm in polynomial time. Optimal and approximated solutions were issued for some specific cases with constraints. One can find the solutions for the cases 1 and 2 machines [4,16] as the initial algorithms. In [16], author solved late works problem using algorithm with setup times included. [4] solve the due works problem on two machines, and can be extended for the case of 3 machines with some conditions on works. Other authors looked at schedule problems in specific cases like [5,8,17]. In this paper, we apply duration automata [1,2] to solve the schedule problem dynamically for the works with uncertain processing time in a cluster computer, which is a system consisting of many computers (computing nodes) co-working together. We solve the schedule problem in a cluster with $m$ machines for two cases: all machines are the same and different in configurations (machine's resources are formally considered as a configuration information, represented by the time need to finish the works). Because of uncertainly processing time, tranditional algorithms can not be used effectively. By using DA model with DA's order criterion, we issue schedule algorithms and practically prove to be better in time consuming compare to FIFO (natural order), the fastest first (greedy) and the longest first (safety) methods without synchronized points.