Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению 09.03.04 Программная инженерия

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Программная система для оптимизации распределения производственных задач

Емельянов Даниил Игоревич

Научный руководитель

Кандидат физико-математических наук

М. В. Лейкин

Нижний Новгород, 2020



Оглавление

Введение

1. Анализ предметной области

1.1 Существующие решения

1.1.1 Katana MRP

1.1.2 Simio

1.1.3 Just plan it

1.2 Продукты для решения оптимизационных проблем

1.2.1 OR-Tools

1.2.2 CP Optimizer

1.2.3 TORSCHE Scheduling Toolbox for Matlab

1.3 Мобильные платформы

Выводы по главе

2. Проектирование системы для оптимизации распределения производственных задач

2.1 Функциональные требования

2.1.1 Сервер

2.1.2 Панель администратора

2.1.3 Мобильное приложение

2.2 Архитектура приложения

2.2.1 Сервер

2.2.2 Мобильное приложение

2.3 Инструменты разработки

2.3.1 Языки программирования

2.3.2 Библиотеки

2.3.2.1 Сервер

2.3.2.2 Панель администратора

2.3.2.3 Мобильное приложение

Выводы по главе

3. Особенности реализации системы

3.1 Оптимизация

3.2 Сервер

3.3 Панель администратора

3.4 Мобильное приложение

3.5 Тестирование

Выводы по главе

Заключение

Список литературы

Приложения

1. Исходный код



Введение

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

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

? Системы учета и распределения ресурсов

? Системы отслеживания и распределения задач

Данные категории предоставляют множество программ, которые в разной степени автоматизируют процессы. Например, одни программы позволяют только учитывать ресурсы, а другие вместе с учетом могут их распределять и предоставляют возможность автоматического заказа ресурсов, когда их становится мало. Так же и с программами, связанными с задачами: не все предоставляют возможность автоматизированного распределения задач, многие из них выполняют простые функции, например, создание, назначение и отслеживание. У распределения задач также бывает несколько типов, например, распределение, основанное на правилах или на разных критериях (продолжительность работ, цена, и.т.д). Основная проблема существующих решений - это их дороговизна, поэтому их могут позволить только крупные компании.

Целью данной работы является программная система для оптимизации выполнения заказов в производственной компании. Каждый заказ состоит из набора товаров. Товары, в свою очередь, представляют собой совокупность задач, которые необходимо выполнить, чтобы товар был готов. Полученная система должна позволить заменить ручной способ ведения бизнеса, который заключался в том, что менеджеру было необходимо вручную из полученных задач составлять неоптимальное расписание.

Итоговая программа должна будет состоять из сервера, панели администратора и мобильного приложения. Система позволит администратору отслеживать все состояния системы; продавцы смогут создавать заказы и настраивать товары под покупателей; а работники будут отслеживать свои задачи. Кроме этого, система будет оптимизировать распределение задач, чтобы сократить общее время производства.

Для достижения поставленной цели, требуется:

1. Проанализировать область систем для распределения производственных задач и их оптимизации.

2. Изучить создание панелей для администратора и сервера.

3. Продумать архитектуру системы.

4. Разработать необходимые компоненты.

5. Протестировать и оценить полученные компоненты.

Дипломная работа состоит из трех глав:

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

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

Третья глава демонстрирует особенности реализации таких компонентов, как: оптимизация, сервер, панель администратора и мобильное приложение.



1. Анализ предметной области

оптимизация программный сетевой сервер

1.1 Существующие решения

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

1.1.1 Katana MRP

Данный продукт предоставляет большой набор инструментов для бизнеса. В его распоряжении есть средства для контроля инвентаря, планирования производства и интеграции с другими сервисами (например, для генерации отчета). Katana позволяет распределять задачи по приоритету. Основной недостаток - это высокая цена, что значительно снижает количество компаний, которые могут себе позволить.

Рисунок 1 Интерфейс Katana MRP



1.1.2 Simio

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

Рисунок 2 Интерфейс Simio

1.1.3 Just plan it

Just plan it специализируется на составлении расписаний для производства в стиле рабочего цеха. Данная система также позволяет выставлять приоритет заказам и интегрировать данные в MRP системы.



Рисунок 3 Интерфейс Just plan it

1.2 Продукты для решения оптимизационных проблем

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

1.2.1 OR-Tools

OR-Tools - это программный комплекс от Google, содержащий в себе разнообразные алгоритмы для решения различных оптимизационных задач, таких, как: построение маршрутов и расписаний. Основные преимущества данного комплекса - это подробная документация, легкость в использовании и открытый исходный код. В дальнейшем для составления расписания я буду использовать именно его.



1.2.2 CP Optimizer

Данная программа от IBM специализируется на инструментах для планирования и составления расписаний. CP Optimizer поддерживают широкую настройку разных ограничений. Также она является частью некоторых программ от IBM, например: ILOG CPLEX Optimization Studio.

1.2.3 TORSCHE Scheduling Toolbox for Matlab

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

1.3 Мобильные платформы

Прежде чем разрабатывать мобильное приложение для продавцов и работников необходимо выбрать мобильную платформу. На данный момент популярны две платформы: Android и iOS, которые занимают 70% и 28% рынка соответственно (Рисунок 4). Данное распределение может быть обосновано следующим: во-первых, дешевизной смартфонов (Android могут использовать разные вендоры, а iOS используется только в продукции Apple). Во-вторых, простота разработки: для разработки под Android можно использовать любую операционную систему, а чтобы выложить приложения в Play Market, необходимо разово заплатить 25$. В тоже время, чтобы начать разрабатывать под iOS, необходимо иметь операционную систему OS X, а для публикации в Apple Store нужно иметь подписку стоимостью в 99$/год.



Рисунок 4 Популярность мобильных операционных систем

Выводы по главе

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



2. Проектирование системы для оптимизации распределения производственных задач

2.1 Функциональные требования

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

2.1.1 Сервер

Сервер должен обладать следующими функциями:

1. Сохранять данные, полученные от клиентов.

2. Создавать товары и задачи.

3. Составлять и оптимизировать расписание задач.

2.1.2 Панель администратора

Панель должна позволять данные функции:

1. Авторизовываться как администратор.

2. Создавать и редактировать тип работников.

3. Создавать и редактировать шаблоны товаров.

4. Создавать и редактировать шаблоны задач.

5. Создавать заказы, выбирая товары и задачи к ним.

6. Просматривать товары к заказам.

7. Просматривать задачи к товарам.

8. Просматривать расписание с задачами.

2.1.3 Мобильное приложение

Мобильное приложение будет обладать следующими функциями:

1. Авторизовываться как продавец или работник.

2. Просматривать заказы, товары и задачи, создавать новые.

3. Просматривать назначенный на работника рабочий график.

2.2 Архитектура приложения

2.2.1 Сервер

Архитектура сервера состоит из трех частей: маршрутизация, бизнес-логика и данные. Маршрутизация отвечает за обработку запросов, проверку на наличие обязательных параметров и передачу данных на следующий уровень. Бизнес-логика занимается обработкой данных, созданием товаров и заданий к ним, а также составлением и оптимизацией расписания. Часть, отвечающая за данные, включает в себя базу данных и модели данных.

2.2.2 Мобильное приложение

В качестве архитектуры для мобильного приложения был выбран паттерн MVVM (Model-View-ViewModel).

Рисунок 5 Архитектура MVVM

Данная архитектура состоит из следующих компонентов:

? View - пользовательский интерфейс. В моем случае это фрагменты (например, для отображения списка заказов).

? Model - бизнес-логика программы. Отвечает за запросы к серверу и обработку данных.

? ViewModel - связующее звено между View и Model. Обрабатывает события, приходящие от View, и передает команды в Model.



2.3 Инструменты разработки

2.3.1 Языки программирования

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

Для написания панели администратора используется JavaScript. Данный язык является самым популярным для написания веб-сайтов, благодаря чему можно найти решение на большинство возникающих проблем.

2.3.2 Библиотеки

Ниже приведен список библиотек, которые применяются при разработке приложения.

2.3.2.1 Сервер

Таблица 1

Инструменты для сервера

Библиотека	Описание
Ktor	Фреймворк для создания асинхронных серверов
Exposed	ORM библиотека для работы с базами данных
Ortools	Библиотека для решения оптимизационных задач
Postgresql-jdbc	Адаптер к PostgreSQL
HikariCP	Пул соединений для JDBC

Логика сервера основывается на библиотеке ktor, которая позволяет сделать REST сервер. В качестве средств для оптимизации расписания применяется OR-Tools, с помощью которой, используя программирование с ограничениями, можно составлять расписания.

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

object ItemTemplates: Table() {

val id = integer("id").autoIncrement()

val title = varchar("title", 512)

override val primaryKey = PrimaryKey(id)

}

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

override suspend fun deleteItemTemplate(id: Int) {

dbQuery {

ItemTemplates.deleteWhere {

ItemTemplates.id eq id

}

}

}



2.3.2.2 Панель администратора

Таблица 2

Инструменты для панели администратора

Библиотека	Описание
react	Предоставляет возможность создавать интерфейсы, используя модульный стиль
material-ui	Содержит в себе готовые react компоненты
react-big-scheduler	React компонент для отображения расписания
react-admin	Фреймворк для построения панелей администратора

Для реализации панели администратора была выбрана библиотека react-admin, позволяющая для создания интерфейса использовать react и его компоненты, а также упрощающая взаимодействие с сервером. Для отображения расписания задач используется компонент react-big-scheduler, который можно настраивать под любые задачи и расширять.

2.3.2.3 Мобильное приложение

Таблица 3

Инструменты для мобильного приложения

Библиотека	Описание
androidx	Библиотека, содержащая в себе основные компоненты для разработки android приложений: элементы интерфейса, навигация.
retrofit2	HTTP-клиент
gson	Библиотека для сериализации/десериализации JSON
paperdb	Удобное хранилище типа ключ/значение

Приложение использует стандартную библиотеку androidx для реализации архитектуры и основных экранов. Retrofit2 предоставляет широкие возможности для работы с сервером. Paperdb используется для хранения сессионной информации, например, токена.

Paper.book().write(TOKEN, loginJsonModel.token)

Выводы по главе

В данной главе были составлены требования, сформирована архитектура и выбраны инструменты для разработки.



3. Особенности реализации системы

3.1 Оптимизация

Основная цель данной системы - это оптимизация распределения задач. В основе этой задачи лежит проблема открытого цеха (job shop), которая заключается в следующем: у нас есть m работников, n работ (), состоящих из задач ( - задача работы ), которые должны быть выполнены последовательно. Задача - построить расписание, которое минимизирует продолжительность всего процесса ().

, где

- время начала выполнения задачи

- время, которое нужно на выполнении задачи

Чтобы решить данную проблему, ее представляют в виде дизъюнктивного графа, где

V - множество вершин, соответствующие задачам. Каждая вершина имеет вес, равный времени, необходимому для выполнения задачи. Добавляются также две фиктивные вершины s и t, представляющие начальное и конечное время.

C - множество соединительных дуг между i и (i+1) задачами.

D - множество дизъюнктивных дуг между задачами, которые должны быть обработаны одним и тем же работников.

Продолжительность работ задается самым длинным взвешенным путем от s до t. Данный путь называется критическим.

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

Математическая модель представляет собой следующее:

, где

- работник, который может выполнять k задачу

S - множество конечных задач для всех работ.

Целевая функция определена в (1). Ограничение (2) означает, что целевая функция должна быть больше или равна общему времени, необходимому для обработки задач из S. Ограничение (3) определяет порядок выполнения задач в работе. Ограничение (4) определяет порядок задач у работников. Начало любой задачи выражено в (5).

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

Основные задачи идут последовательно, администратор выбирает заранее порядок этих задач. Дополнительные задачи должны выполняться после обязательных. Администратор также может выбирать порядок дополнительных задач, и их разветвленность. В отличие от обязательных задач, дополнительные могут не иметь конкретной зависимости, тогда алгоритм автоматически будет их выбирать после обязательных.

Для решения данной оптимизационной задачи используется библиотека OR-Tools. В основе данной библиотеки лежит CP-SAT решатель, который реализует локальный поиск и программирование ограничениями (Constraint programming).

Используя инструменты, которые предоставляет OR-Tools, я выставляю ограничения для нашей системы.

Во-первых, это - ограничения, представленные выше для задачи открытого цеха.

Во-вторых - для обязательных задач мы учитываем зависимости.

, где

- индекс задачи, от которой зависит задача .

- набор задач для работы.

В-третьих, дополнительные задачи должны идти после обязательных и после зависимостей.

и

, где - индекс дополнительной задачи

- индекс задачи, от которой зависит дополнительная задача.

m - индекс обязательной задачи.



3.2 Сервер

Сервер предоставляет на выход 22 точки доступа, их общее описание дано в таблице 5.

Таблица 4

Точки доступа на сервере

Путь ресурса	HTTP-методы	Назначение
users/login	POST	Авторизоваться, чтобы получить доступ к остальным ресурсам
users/create	POST	Создать пользователя
users/delete	DELETE	Удалить пользователя
item-templates	POST, GET, DELETE, PUT	Создать, получить, удалить или отредактировать шаблоны товаров
task-templates	POST, GET, DELETE, PUT	Создать, получить, удалить или отредактировать шаблоны задач
orders	POST, GET, DELETE, PUT	Создать, получить, удалить или отредактировать заказы
items	GET	Получить список товаров
tasks	GET	Получить список задач
worker-types	POST, GET, DELETE, PUT	Создать, получить, удалить или отредактировать типы работников
schedule	GET	Получить данные о распределении задач

На каждый запрос сервер отправляет JSON ответ. Для доступа к ресурсам необходимо сначала авторизоваться и получить токен.

Для создания точки доступа с помощью библиотеки ktor необходимо создать расширение к классу Route. Например, ниже представлен код для обработки метода GET на получение списка шаблона товаров:

const val ITEM_TEMPLATES = "$API_VERSION/item-templates"

@Location(ITEM_TEMPLATES)

class ItemTemplatesRoute

fun Route.itemTemplatesRoute(db: ItemTemplateRepository) {

authenticate("jwt") {

get<ItemTemplatesRoute> {

try {

val itemTemplates = db.getItemTemplates()

call.respond(itemTemplates)

} catch (e: Throwable) {

application.log.error("Failed to get ItemTemplates", e)

call.respond(HttpStatusCode.BadRequest, "Problems getting ItemTemplates")

}

}

}

}

3.3 Панель администратора

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

Панель содержит следующие разделы:



Рисунок 6 Меню панели администратора

На экране Заказы можно просматривать и удалять заказы, а также создавать их, составляя список товаров в заказе.

Рисунок 7 Интерфейс создания заказа

На экране “Товары” можно просматривать товары, которые относятся к заказам. На экране “Задачи” отображается список задач, которые нужно выполнить, чтобы товары были готовы. Экран “Типы работников” позволяет создавать и удалять типы работников. “Шаблоны товаров” нужны для создания и удаления шаблонов товаров, которые компания может произвести. “Шаблоны заданий” позволяют создавать шаблоны заданий, относящиеся к товарам.

Рисунок 8 Список шаблонов заданий

Библиотека react-admin делает проще создание необходимых экранов, благодаря использованию react стиля. Например, ниже представлен код для создания таблицы со списком шаблонов заданий.

export const TaskTemplateList = props => (

<List {...props}>

<Datagrid rowClick="edit">

<TextField source="id" />

<ReferenceField label="itemTemplateId" source="itemTemplateId" reference="item-templates">

<TextField source="title" />

</ReferenceField>

<ReferenceField label="taskTemplateDependencyId" source="taskTemplateDependencyId" reference="task-templates">

<TextField source="title" />

</ReferenceField>

<ReferenceField label="workerTypeId" link="show" source="workerTypeId" reference="worker-types">

<TextField source="title" />

</ReferenceField>

<TextField source="title" />

<NumberField source="timeToComplete" />

<BooleanField source="isAdditional" />

</Datagrid>

</List>

);

На экране “Расписание” можно посмотреть распределение задач у работников (задачи отображаются либо по часам, либо по дням). Каждому товару присваивается уникальный цвет, которым выделяются все задачи этого товара. Данное выделение позволяет легче понимать состояние создания товара на экране расписания. Также при составлении расписания учитываются выходные дни, поэтому задачи распределяются только на рабочие часы.



Рисунок 9 Расписание задач

3.4 Мобильное приложение

Мобильное приложение работает в двух состояниях: для продавца и для работника. При авторизации сервер отправит нам данные, в которых указывает, кто вошел в аккаунт.

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



Рисунок 10 Экраны приложения в режиме Продавец

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

Рисунок 11 Экраны приложения в режиме Работник

3.5 Тестирование

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

1. Продавец создает заказ.

2. Продавец удаляет заказ.

3. Работник запрашивает список задач.

4. Работник меняет статус задачи.

5. Администратор создает шаблон товара.

6. Администратор создает шаблон задания.

7. Администратор создает тип работника.

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

На вход были поданы следующие данные

? Работа 0 =

? Работа 1 =

? Работа 2 =

В данном примере каждая работа состоит из списка задач, где первый элемент - это тип работника, а второй элемент - время, необходимое на выполнение задачи.

Мы можем вручную расставить задачи следующим образом и получить решение длиной в 12. Но данное решение не будет оптимальным.

В данном примере, по оси y отображены типы работников.

Разработанная мной система на этих данных смогла найти оптимальное решение, длинной в 11.

Из данной проверки можно сделать вывод, что система способна построить оптимальное распределение задач, чтобы сократить общее время производства.

Выводы по главе

В последней главе были рассмотрены компоненты системы и их особенности.



Заключение

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

1. Сервер для хранения и обработки информации (создание заказов, составление расписания).

2. Панель администратора для управления системой.

3. Мобильное приложение для продавцов и работников.

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



Список литературы

1. KatanaMRP [Электронный ресурс] URL: https://katanamrp.com/

2. Simio [Электронный ресурс] URL: https://www.simio.com/index.php

3. Just Plan It [Электронный ресурс] URL: https://www.just-plan-it.com/

4. OR-Tools [Электронный ресурс] URL: https://developers.google.com/optimization

5. CP Optimizer [Электронный ресурс] URL: https://www.ibm.com/analytics/cplex-cp-optimizer

6. TORSCHE Scheduling Toolbox for Matlab [Электронный ресурс] URL: https://rtime.felk.cvut.cz/scheduling-toolbox/

7. Mobile Operating System Market Share Worldwide [Электронный ресурс] URL: https://gs.statcounter.com/os-market-share/mobile/worldwide

8. Google Play Console [Электронный ресурс] URL: https://play.google.com/apps/publish/

9. Apple Developer Program [Электронный ресурс] URL: https://developer.apple.com/programs/how-it-works/

10. MVVM Framework [Электронный ресурс] URL: https://docs.devexpress.com/WPF/15112/mvvm-framework

11. TIOBE Index [Электронный ресурс] URL: https://www.tiobe.com/tiobe-index/

12. Peter Brucker: Scheduling Algorithms // Springer, 2004

13. The Job-Shop Problem, the disjunctive model and benchmark data [Электронный ресурс] URL: https://acrogenesis.com/or-tools/documentation/user_manual/manual/ls/jobshop_def_data.html



Приложения

1. Исходный код

Программный код находится в трех репозиториях:

? Сервер: https://github.com/Defolters/TaskDistributionBack

? Панель администратора: https://github.com/Defolters/TaskDistributionAdmin

? Мобильное приложение: https://github.com/Defolters/TaskDistribution

Размещено на Allbest.ru