45
установлен порядок взаимодействия с облачными технологиями для
осуществления успешного планирования.
46
ГЛАВА 3. СОВМЕСТНОЕ ПЛАНИРОВАНИЕ
РАБОТЫ КОЛЛЕКТИВА
3.1. Применение метода оптимизации при распределении
заданий для сотрудников
Предполагается, что руководитель, который одновременно является и
ИТ администратором, успешно собрал данные о количестве рабочего
времени, а также о степени готовности работ. Далее, на основе информации о
имеющихся задачах, а именно, о приоритете выполнения и длительности
выполнения каждой задачи каким-либо из сотрудников, требуется создать
оптимальное расписание выполнения задач на 3 дня.
Модель задачи оптимизации календарного планирования по времени
представлена ранее в секции 2.2 предыдущей главы. Исходная задача для
произвольного количества дел, n, имеет вид:
а
11
х
1
+ а
12
х
2
+ ... + а
1n
х
n
≤ 720, (3.1)
а
21
х
1
+ а
22
х
2
+ ... + а
2n
х
n
≤ 720, (3.2)
а
31
х
1
+ а
32
х
2
+ ... + а
3n
х
n
≤ 720, (3.3)
х
i
≤ x
imax
, (3.4)
F = к
1
х
1
+ к
2
х
2
+ … + к
n
х
n
= max, (3.5)
x
1,
x
2,…
x
n
≥ 0, (3.6)
где а
ij
–
коэффициенты трудности, выраженные в единицах [время/кол.
единиц работы] (константы);
х
imax
– требуемое выполнение количества единиц работы;
n – количество сотрудников;
х
i
– количество единиц работы сотрудника i;
F – функция полезности;
к
1
,...к
n
– коэффициенты важности (константы).
47
Задача решается с использованием методов линейного
программирования, а именно введением искусственного базиса [6], согласно
которому строится вспомогательная задача:
Phi = y
1
+ y
2
+ y
3
= min, (3.7)
а
11
х
1
+ а
12
х
2
+ ... + а
1n
х
n
+ y
1
= 720, (3.8)
а
21
х
1
+ а
22
х
2
+ ... + а
2n
х
n
+ y
2
= 720, (3.9)
а
31
х
1
+ а
32
х
2
+ ... + а
3n
х
n
+ y
3
= 720, (3.10)
x
i
≤ x
imax
, (3.11)
x
1,
x
2,…
x
n
≥ 0; y
1,
y
2,
y
3
≥ 0. (3.12)
где Phi – функция полезности двойственной задачи;
y
1
, y
2
, y
3
– искусственные переменные.
Сумма y
1
+ y
2
+ y
3
выражается из системы ограничений, в результате
уравнение (3.7) преобразуется в
Phi = 2160 – ∑ (a
i1
x
1
+ a
i2
x
2
+ … + a
in
x
n
) . (3.13)
Как видно из сравнения уравнений (3.5) и (3.13) функции Phi и F
равны при установления соответствия коэффициентов важности и
коэффициентов трудности. Таким образом вспомогательная задача и
исходная задача эквивалентны.
В свою очередь вспомогательная система решается симплекс методом
[11]. Составляется симплекс-таблица, при составлении которой полагается,
что исходные переменные x
1
, x
2 ...
х
n
являются небазисными, а введённые
искусственные переменные, y
1
, y
2
, y
3
– базисными, т. е. значения x
1
, x
2 ...
х
n
могут быть выражены из линейных сумм введенных переменных y
1
, y
2
, y
3
.
Вообще говоря, требуется n дополнительных переменных y для
однозначного выражения n переменных x. Поэтому вводятся y
4
, ..., y
n+3
,
которые преобразуют выражение (3.11) в выражение:
x
i
+ y
i+3
= x
imax
, i = 1,…,n. (3.14)
48
Для того, чтобы выразить каждое из значений x
i
через линейную
сумму y
1
, y
2
, ..., y
n+3
используется метод преобразований Гаусса-Жордана,
как будет показано далее.
Итак, исходная симплекс-таблица (таб. 1) выглядит следующим
образом:
Таблица 1
Симплекс-таблица нулевой итерации
x
1
x
2
...
x
n
y
1
y
2
y
3
...
а
11
а
12
...
а
1n
1
0
0
...
720
а
21
а
22
...
а
2n
0
1
0
...
720
а
31
а
32
…
а
3n
0
0
1
...
720
...
...
...
...
...
...
...
...
...
-∑
i
a
i1
-∑
i
a
i2
…
-∑
i
a
in
0
0
0
0
Начальное опорное решение
1
= (0,0,…,0; 720, 720, 720, x
imax
, ...,
x
imax
). Среди чисел -∑
i
a
i1
, -∑
i
a
i2
, ..., -∑
i
a
in
в таблице 1 выбирается наибольшее
число, что соответствует некоторому индексу j, так называемую
положительную оценку
j
= -∑a
ij
, и составляются следующие отношения:
720/a
1j
, 720/a
2j
, 720/a
3j
, x
imax
/a
ij
. Находится наименьшее среди последних,
соответствующее строке с индексом l=1, 2, ... n, например l=2, и выполняется
жорданово преобразование всей таблицы с ведущим элементом а
2j
. В
результате получается симплекс-таблица второго порядка (табл. 2):
Таблица 2
Симплекс-таблица первой итерации
x
1
…
x
j
...
x
n
y
1
y
2
y
3
...
а
11
*а
2j
–
а
21
*а
1j
…
0
...
а
1n
*а
2j
–
а
2n
*а
1j
а
2j
-а
1j
0
...
720*а
2j
-
720*а
1j
а
21
…
а
2j
...
а
2n
0
1
0
...
720
а
31
*а
2j
–
а
21
*а
3j
…
0
…
а
3n
*а
2j
–
а
2n
*а
3j
0
-а
3j
а
2j
...
720*а
2j
-
720*а
3j
...
...
0
...
...
...
...
...
...
...
-∑
i
a
i1
*а
2j
+
а
21
*∑
i
a
ij
…
-∑
i
a
ij
…
-∑
i
a
in
*а
2j
+
а
2n
*∑
i
a
ij
0
∑
i
a
i3
0
720*∑
i
a
ij
49
Данная процедура повторяется до тех пор пока все коэффициенты в
последней строке таблицы 2 не станут неположительны. Если этого не
происходит, то итерации расходятся – решения нет. При наступлении же
случая когда все коэффициенты в последней строке не положительны,
получается оптимальное решение. В этом решении ненулевые решения
соответствуют переменным, для которых в последней строке присутствует
нулевое значение. Таким образом, для тех переменных x
j
, для которых ∑
i
a
ij
=
0, имеем оптимальное решение канонической задачи минимизации x
j
=
(значение в последнем столбце в к-й строке)/а
кj
. Таким образом получается
решение вспомогательной задачи (3.7) - (3.12), в которой производится
оценка времени, затраченного на осуществление намеченных дел.
3.2. Создание автоматизированной системы
планирования
Согласно индивидуальному заданию ВКР необходимо разработать
программный продукт календарного планирования, позволяющий вносить
данные о делах, формировать списки и отчеты по полученным данным;
организовать напоминание о предстоящих событиях, организовать защиту и
синхронизацию информации с помощью онлайн-органайзера Google
Календарь.
Разрабатываемая программа, предназначена для построения
оптимального по временным параметрам списка задач необходимых к
завершению в ближайшие 3 дня планирования. В связи со спецификой
работы на предприятии под задачей понимается построение расписания
конкретного работника.
Решение задачи календарного планирования симплекс методом было
реализовано в программе на языке СИ [9], приведенной в приложении А, в
50
процедуре optim. В программе помимо метода оптимизации реализована
система записи нескольких задач в память компьютера посредством ввода с
клавиатуры или считывания из файла. Для того, чтобы проверить работу
программы на языке СИ, потребуется скачать компилятор и установить его
на компьютере на диске С:.
Программа была написана и отлажена с использованием компилятора
Borland Turbo С++ 3.1 [23]. Компилятор доступен для скачивания в интернете
например по адресу: http://alexeypetrov.narod.ru/Distrib/distrib.html. Данный
компилятор, работающий в среде DOS, был выбран в следствие удобства и
простоты работы, а также доступности для бесплатного скачивания в сети
Интернет.
Если используется операционная система Windows, то для запуска
Borland С++ потребуется установить программу DOSBox. Это эмулятор DOS.
После установки и при каждом новом запуске требуется ввести в консоль
DOSBox команду mount c C:\ для того, чтобы смонтировать в эмулятор С: как
раздел жесткого диска. Иначе при запуске Borland С компилятор не найдёт
свои библиотеки. Для пользователей Linux требуется предварительно
установить сначала программу Wine, а затем DOSbox. На рисунке 13
представлено окно программы Borland Turbo С++ 3.1 с загруженной
программой calendar.c, листинг которой приведён в приложении А.
Для доступа к программному проекту необходимо выполнить
следующие операции:
- скомпилировать исходный программный код;
- запустить exe файл.
Структурная диаграмма программы приведена на рисунке 14. После
входа в систему отображается главное меню, отображённое на диаграмме
стадией работы «выбор действия». С главного меню, осуществляется запуск
ввода с клавиатуры, удаления, вывода на экран, сохранения задач, а именно,
51
в главном меню спрашивается ввести число от 1 до 7: 1 - для ввода новой
задачи в память; 2 - для удаления задачи из памяти; 3- для вывода на экран
задач, находящихся в памяти; 4 - для записи данных из памяти в файл; 5 - для
загрузки данных из файла в память; 6 - для поиска данных в памяти по
названию задачи; 7 - для оптимизации порядка выполнения задач,
загруженных в память, в ближайшие 3 дня.
Введя число 1 пользователь заносит информацию о конкретном
сотруднике в память компьютера. А именно: информацию о минимальном
времени, которое может быть потрачено работником в день; может-ли он
работать все 3 дня или нужно сделать какие-либо из 3-х дней выходными;
предпочтительную очередность несения дежурств по дням; сложность
работы. Помимо этой необходимой информации, в программу можно внести
такие данные как: является ли дежурство периодичным во времени или нет;
сколько это стоит денег; является ли задание частично начатым в прошлом,
если да, то сколько работы уже было сделано.
Рисунок 13 – Компилятор Turbo C++
52
Информацию можно сохранить в файл todolist.txt при нажатии на 4 в
главном меню.
После этого пользователь имеет возможность создать 3-х дневное
расписание оптимизированное по времени и важности посредством нажатия
на 7 в главном меню. Все промежуточные симплекс-таблицы, получаемые на
каждом шаге оптимизации, записываются в файл optim.txt. В случае
расхождения симплекс-итераций информация о невозможности решения
задачи также отображается на экране. После получения оптимального
решения на экране отображается дела и в каком объёме требуется выполнить
в 1-й день, во 2-й и 3-й начиная с даты проведения оптимизации.
Главное меню автоматически выводиться на экран после завершения
операции произведённой на предыдущей стадии в главном меню как видно
на рисунке 14.
Рисунок 14 – Структурная диаграмма программы
оптимизации
Полный текст программы, приведёный в приложении А, довольно
громоздок, поэтому нет никакой возможности описать все подробности
алгоритма. Здесь будет приведено только краткое описание организации
программы, приведены ссылки на соответствующую литературу и описаны
входные и выходные данные.
53
В памяти компьютера выделяется пространство под массив структур
st, которые служат для записи задач, вводимых пользователем. Экземпляры st
структуры castsk объявлены в начале программы – сначала определяются все
типы данных объеденённых в структуру castsk, а затем создаются
экземпляры st. Максимальное количество вводимых задач (сотрудников) не
может превышать 100.
Данный подход структурирования данных по существу является
объектно-ориентированным программированием в языке СИ [10]. Это
аналогично объектно-ориентированному программированию в С++ [16].
Идея заключается в использовании связанного списка структур, широко
применяемого в программировании. Реализация записи задач сводится к
организации списка экземпляров структур, связанных между собой
указателями [14]. Такая запись позволяет создавать плотные списки без
пустых интервалов между записями, что важно для процедуры оптимизации.
При такой реализации, не требуется запись и чтение данных с жесткого
диска, вся информация хранится в оперативной памяти. Программирование с
использованием указателей требует учёта особенностей компиляторов, так
например в gcc требуется преобразование типа адреса указателя в тип (void
*) при использовании функции print для распечатки на экране [33].
Аналогично существуют особенности для компиляторов Microsoft Visual
Studio [1].
В программе используется ещё одна структура, ctrl – структура
контроля, которая хранит указатели на начало и конец связанных структур st,
а также количество введенных пользователем структур.
Процедура optim будет рассмотрена более детально - будут
приводиться отрывки кода с подробным описанием. В начале процедуры
идёт объявление всех используемых переменных и процедур, объявленных
54
внутри данной процедуры. В частности в начале процедуры производится
объявление указателя *ptr, который имеет тип castsk...
int optim(void)
{
...
struct castsk *ptr;
...
FILE *fp;
int calcdates(unsigned int *ndays);
Как видно в процедуре optim используется внешняя процедура
calcdates, которая требуется если пользователь выставляет конечные даты
заданий-дежурств на срок более 3-х дней от момента проведения
оптимизации, что понимается как «в течении ближайших 3-х дней у таких
сотрудников нет выходных». calcdates вычисляет максимальное количество
дней до конечной даты всех заданий-дежурств, что требуется для процедуры
оптимизации.
В данной программе, экземпляры структур объявлены глобальными
переменными, а значит нет надобности передачи их в процедуру через
параметры, поэтому имеем в списке параметров процедуры слово void. Это
слово необходимо использовать для Borland C++ 3.1 [27].
В следующем фрагменте кода производится объявление и открытие
файла optim.txt, в который будут записываться все промежуточные симплекс-
таблицы и результаты оптимизации...
fp = fopen("optim.txt","w");
Производится присвоение локальному указателю ptr адреса начала
связанного списка задач ctrl.bbeg, тем самым данный указатель используется
для получения экземпляра структуры, который будет удалён при выходе из
процедуры...
ptr = ctrl.bbeg;