Теория расписаний

Министерство образования и науки, молодежи и спорта Украины

Севастопольский национальный технический университет

Кафедра кибернетики и вычислительной техники

Пояснительная записка к курсовой работе

по дисциплин: «Вычислительный практикум»

Севастополь

Содержание

Введение

.        Постановка задачи

.        Описание алгоритма

.        Описание программы

.        Тестовые примеры

.        Анализ результатов эксперимента

Заключение

Литература

Приложение A

Введение

На современном этапе развития экономики и частного предпринимательства возникает задача повышения уровня автоматизации обработки больших объемов информации. Значительную роль в обработке такой информации играет упорядочивание процессов ее обработки, поскольку обработка занимает большое количество времени.

Немаловажную роль в обработке информации играет последовательность выполнения поступающих заданий, данная проблема актуальна для серверов, предоставляющих свои ресурсы в сети.

При решении данной задачи в рассматриваемой системе необходимо закрепить решаемые задачи за ЭВМ и установить порядок их выполнения во времени.

В данной курсовой работе рассматривается одна из задач теории расписаний - составление оптимального расписания, где критерием оптимальности служит минимальное значение функции штрафа. Данная задача является классической задачей упорядочения - наиболее изученного класса задач теории расписаний. В этих задачах распределений задач по ЭВМ и длительности их выполнения предполагаются заданными. Необходимо указать наиболее эффективную стратегию управления очередями задач на выполнение каждой ЭВМ.

Таким образом, решение задачи может быть получено в результате рассмотрения конечного числа расписаний, определяемых возможными последовательностями обслуживания требований. Такие расписания называются перестановочными. Если множество N не упорядочено, то число перестановочных расписаний n!.

.       
Постановка задачи

алгоритм программ расписание

Пусть n требований обслуживается одной ЭВМ. Все требования поступают на обслуживание в момент времени d=0. Длительность обслуживания требования k равна tk единиц времени. Если требование k обслуживается первым, то для подготовки прибора к обслуживанию этого требования необходимо s0k единиц времени, . Если требование j обслуживается непосредственно после требования i, то для перегрузки программного обеспечения ЭВМ необходимо sij единиц времени, 1£i¹j£n. Обслуживание требования k желательно завершить к директивному сроку Dk>=0. Функция штрафа jk(x)=сk*max(x-Dk,0). Требуется организовать так процесс обслуживания требований, чтобы функция штрафа

была минимальной. -фактическое время завершения обслуживания требования k.

.        Описание алгоритма

.        Инициализация данных

.        Выбор начальной расстановки

.        Определение функции штрафа

.        Запомнить текущую расстановку как оптимальную

.        Пока существуют нерассмотренные варианты.         Генерировать следующую расстановку.       Вычислить функцию штрафа.         Если текущая расстановка лучше, запомнить расстановку как оптимальную

.        Вывод данных

Алгоритм работы программы:

Переменные:

c : вектор;

i,j : целое;

Начало::=n-1;

Пока (c[i]>=c[i+1]) i:=i-1;:=n;

Пока (c[j]<=c[i]) j:=j-1;:переставить(i,j);

i:=i+1; j:=n;

Пока (i<j)

н.ц.

c:переставить(i,j);

i:=i+1;:=j-1;

к.ц.

Конец.

3.       Описание программы

Переменные и массивы, используемые в программе:

int n - количество требований;

int [ ] tk - длительность обслуживания требований;

int [ ] dk - директивный срок;

int [ ] c - приоритет выполнения;

int [ ] sigma - подготовка прибора к обслуживанию;

int [ ] tek - текущее расписание;

int [ ] order - порядок обработки заданий;

int [ ] best - оптимальное расписание;

int f - значение функции штрафа;

int perest[ ] - массив перестановок;

Классы и методы используемы в программе:

Класс Perebor выполняет генерацию перестановок с помощью алгоритма полного перебора

·        Метод getPerms возвращает полученные перестановки

·        Метод permut генерирует перестановки

·        Метод vector меняет местами требования согласно алгоритму

·        Метод inv - реверс полученного вектора перестановок

·        Метод factorial вычисляет факториал n

Класс Main содержит главный метод, который управляет работой всей программы

·        Метод f вычисляет для каждой перестановки функцию штрафа

·        Метод main является главным методом программы, который выполняет управление над программой

Пример 1:

Введите n:

Неверный ввод!

Пример 2:

Введите n:

Неверный ввод!!!

Пример 3:

Введите n:

Значения не могут быть отрицательными!

Пример 4:

Введите n: 3

Ввод длительности обслуживания требования tk(3): 3 4 5

Ввод директивных сроков dk(3): 4 5 6

Ввод времени на подготовку каждого требования и время на перезагрузку ЭВМ sigma(3*3):

4 5 4 5 6 1 3 4

Ввод приоритетов c(3): 4 5 6

Решение с помощью алгоритма полного перебора:

Перестановка: Функция

штрафа

[0, 1, 2]: 83

[1, 0, 2]: 122

[0, 2, 1]: 71

[2, 0, 1]: 100

[1, 2, 0]: 102

[2, 1, 0]: 116

Минимальная функция штрафа: 71, при порядке: [0, 2, 1].

Время выполнения: 60 мc.

Пример 5:

Введите n: 3

Ввод длительности обслуживания требования tk(3): 0 0 0

Ввод директивных сроков dk(3): 0 0 0

Ввод времени на подготовку каждого требования и время на перезагрузку ЭВМ sigma(3*3):

0 0 0 0 0 0 0 0

Ввод приоритетов c(3): 0 0 0

Решение с помощью алгоритма полного перебора:

Перестановка: Функция

штрафа

[0, 1, 2]: 0

[1, 0, 2]: 0

[0, 2, 1]: 0

[2, 0, 1]: 0

[1, 2, 0]: 0

[2, 1, 0]: 0

Минимальная функция штрафа: 0.

Время выполнения: 7 мc.

.        Анализ результатов эксперимента

Проверка решения вручную:

Не целесообразно проверять 16 перестановок. Проверим значение функции штрафа для перестановки 0, 1, 2, 3, . Также возьмем наугад любую перестановку и посчитаем её функцию штрафа вручную. Если, результат решения вручную будет соответствовать результату решения программы, то работу программы будем считать верной.

Разместим исходное время и коэффициенты в порядке выполнения программ [0,1,2,3].

tk: 9, 2, 5, 7

Ck:2, 3, 4, 1

Вычислим значения фактического времени прохождения программ.

kt: 11, 16, 26, 38

Вычитаем из фактического времени t значение D: 10, 10, 10, 10, 10

Вычисляем сумму произведений коэффициентов Ck и времен tk:= 2*1+6*3+16*4+1*38 = 112

Для перестановки [2,1,0,3]

t: 5, 2, 9, 7

С:4, 3, 2, 1

Вычислим значения фактического времени прохождения программ.

t: 6, 11, 21, 38

Вычитаем из фактического времени t значение Dk: 10, 10, 10, 10, 10

Вычисляем сумму произведений коэффициентов Ck и времен t := 2*1+6*3+16*4+1*38 = 112

Также проверим правильность расчета для последней перестановки

«[4, 3, 2, 1, 0]: 29,60».

Разместим исходное время и коэффициенты в порядке выполнения программ.

tk: 7, 7, 3, 7, 12

С: 4, 8, 8, 2, 7

Вычислим значения фактического времени прохождения программ.

t: 7, 7, 3, 7, 12

Вычитаем из исходного времени t значение Dk: 5, 5, 1, 5, 10

Таким образом, программно полученный результат является верным.

По результатам расчета можно сделать вывод, что минимальное время выполнения заданного числа программ в срок равно 3 полученное для двух последовательностей - 1, 3, 2 и 3, 2, 1. Результат программы - максимальное кол-во программ, которое может быть выполнено за данные сроки 3, 1, 2.

Точные значения времени необходимые для определения оптимальной последовательности при заданном количестве требований приведены в таблице:

Из графика и таблицы видно, что время выполнения программы прямо пропорционально зависит от числа требований. При увеличении числа требований затраченное время возрастает по нелинейной зависимости.

Заключение

Разработанная программа позволяет решить задачу планирования работы, когда требования необходимо реализовать на ЭВМ, в условиях поступления на выполнение задания из n требований.

Основной деталью организации работы программы является рекурсивное выполнение главной процедуры, что ведет к существенному сокращению времени перебора.

Тестовые примеры показали, что программа работает правильно и обладает достаточным быстродействием. В целях предотвращения осложнения при тестовой проверке рекомендуется задавать небольшие значения n.

Программа была написана на языке программирования высокого уровня Java в среде BlueJ.

Литература

1.   Скатков А. В. Методические указания по курсовому проектированию по дисциплине «Вычислительный практикум» для студентов заочной формы обучения специальности 6.05010201 [Текст]: учеб. пособие / Сергеев Г. Г., Луговская Л. П. - Севастополь: СевНТУ, 2012. - 23 с.

2.       Ноутон П., Шилдт Г. Java 2: пер. с англ. - СПб.: БХВ-Петербург, 2000. - 1072 с.: ил.

.        Конвей Р.В., Максвелл В.А., Миллер Л.В. Теория расписаний: М.:
Наука, 1975. -300 с.

.        Танаев В.С., Шкурба В.В. Введение в теорию расписаний: М.: Наука,
1975. -256 с.

5.       Сачков В.Н. Вероятностные методы в комбинаторном анализе: М.: Наука, 1978. - 288 с.

Приложение A

java.util.*;class Perebor {

private int[][] perest;int[] p;int n;int k;Perebor(int[] s) {= s.length;= new int[factorial(n)][n];= Arrays.copyOf(s, n);= 0;(n-1);

}int[][] getPerms() {perest;

}void permut(int m) {(m == 0) {

perest[k++] = Arrays.copyOf(p, n);

} else {

for(int i = 0; i <= m; i++) {(m-1);(i < m) {

vector(i, m);

inv(m-1);

}

}

}

}void vector(int a, int b) {t = p[a];[a] = p[b];[b] = t;

}void inv(int m) {i = 0;j = m;(i < j) {

vector(i, j);

i++;

j--;

}

}static int factorial(int n) {res = 1;(int i = 1; i <= n; i++) {

res *= i;

}res;

}

}

java.util.*;java.io.*;java.util.Date;class Main {static void main(String [] args) {

try { //при работе с вводом данных, нужно позаботиться об исключениях

Scanner input = new Scanner(System.in);n;.out.println("Введите n: ");= input.nextInt();(n == 0) {.out.println("Неверный ввод. Перезапустите программу");;

}[]tk = new int[n];.out.println("\n");

System.out.printf("Ввод длительности обслуживания требования tk(%d):\n",n);

for (int i = 0; i < tk.length; i++) {[i] = input.nextInt();

}[]dk = new int[n];.out.println("\n");.out.printf("Ввод директивных сроков dk(%d):\n",n);(int i = 0; i < dk.length; i++) {[i] = input.nextInt();

}[][] sigma = new int[n+1][n];

System.out.println("\n");.out.printf("Ввод времени на подготовку каждого требования и время на перезагрузку ЭВМ sigma(%d*%s):\n",n,n);

for (int i = 0; i < sigma.length; i++) {(int j = 0; j < sigma.length-2; j++) {[i][j] = input.nextInt();

}

}[] c = new int[n];.out.printf("Ввод приоритетов c(%d):\n",n);(int i = 0; i < c.length; i++) {[i] = input.nextInt();

}[] order = new int[n]; //порядок обработки заданийstartTime = System.currentTimeMillis(); //засекаем время(int i = 0; i < n; i++)[i] = i;gen = new Perebor(order); //генерация перестановок

int[][] perest = gen.getPerms(); //заносим полученные перестановки в массив

int min = Integer.MAX_VALUE;[] best = new int[n];

System.out.println("\n\n\nРешение с помощью алгоритма полного перебора:");.out.printf("Перестановка: Функция\n");

System.out.printf(" штрафа\n");(int i = 0; i < perest.length; i++) {v = f(tk, sigma, dk, c, perest[i]);.out.printf("%s: %d\n", Arrays.toString(perest[i]), v);(v < min) {= v;= Arrays.copyOf(perest[i], n);

}

}.out.printf("\nМинимальная функция штрафа: %d, при порядке: %s.\n", min, Arrays.toString(best));timeSpent = System.currentTimeMillis() - startTime;.out.println("Время выполнения: " + timeSpent + " мc.");

}

(InputMismatchException ioe) {.out.println("Неверный ввод!");

}

(NegativeArraySizeException exc) {.out.println("Значения не могут быть отрицательными!");

}static int f(int[] tk, int[][] sigma, int[] dk, int[] c, int[] order) { //метод расчета функции штрафа

int k = tk.length;//длительность обслуживания требованияnow = 0; // текущее времяf = 0; // функция штрафа

for(int i = 0; i < k; i++) {(i == 0)+= sigma[k][order[i]];+= sigma[order[i-1]][order[i]];+= tk[order[i]];+= c[order[i]] * Math.max(now - dk[order[i]], 0);//функция штрафа

}f;//метод возвращает функцию штрафа

}

}