Patent ID: 8881158
Filing Date: 2014-11-04
Classification: G06F

Abstract:
1. A schedule decision device, comprising: dependency acquisition means that acquires dependencies of execution sequences required for a plurality of sub tasks into which a first task has been divided; candidate generation means that generates a plurality of sub task structure candidates that satisfy said dependencies acquired by said dependency acquisition means and for which a plurality of processing devices execute said plurality of sub tasks; superimposition means that categorizes said plurality of sub task structure candidates generated by said candidate generation means as a plurality of groups, selects a first and second sub task structure candidate, compares the execution duration of the selected first and second sub task structure candidates, and adds a duration for which the executaion duration of one the first or second task structure candidate does not match the execution duration of the other task structure candidate to the other task structure candidate; scheduling means that generates a plurality of the first schedule candidates by further assigning at least one second task to each of said sub task structure candidates generated by said superimposition means; effective degree computation means that computes an effective degree that is realized by the effective degree of said first task and the effective degree of said second task for each of said plurality of the first schedule candidates generated by said scheduling means, wherein the computation means performs the step of: wherein the effective degree score for each task is computed according to the following formula: where k3, k4, k5 are weighting coefficients, the average tolerance degree is an average value of tolerance degrees computed according to the following formula:  ,the average interruption time is an average value of times for which a task is interrupted in each execution period, and the average jitter is an average value of delay times after a period starts until a task starts in each execution period, and where k1 and k2 are weighting coefficients; and candidate decision means that decides a schedule candidate used for the executions of said first task and said second task from said plurality of the first schedule candidates based on said effective degrees computed by said effective degree computation means; wherein said effective degree computation means further computes an effective degree of the respective first schedule candidates belonging to said respective sub task structure candidates generated by said superposition means, selects a group of sub task structure candidates from among said groups generated by the said superimposition means based on the computed effective degrees, and computes a plurality of second effective degree scores for a plurality of second schedule candidates corresponding to the sub task structure candidates that belong to the selected group; said candidate decision means decides a second schedule candidate used for the executions of said first task and said second task from said plurality of second schedule candidates based on said second effective degrees computed by said effective degree computation means.