Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 17.11.2015
Сообщений: 26

Посоветуйте как реализовать job shop scheduling

13.01.2018, 17:23. Показов 1351. Ответов 0

Студворк — интернет-сервис помощи студентам
У меня учебный проект, нужно придумать алгоритм для решения проблемы jobshop (https://www.optil.io/optilion/problem/3021)
Для начала можно использовать алгоритм выбора операции с наименьшим временем исполнения. Я попытался.
Сделал программу, но время выполнения оказалось высоким. Если кто-то реализовывал похожие вещи, посоветуйте как попроще делать, а то я накрутил по сложности, деки, объекты и т.д
Спасибо за Ваше время!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
// JobShop_2.0.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <windows.h>
 
using namespace std;
 
struct Operation {
    int num;
    int time;
};
 
struct OperationQueue {
    int start;
    int task_num;
    int time;
    int wait;
    int priority;
};
 
class Machine {
private:
    bool state;
    int operation_num;
    deque<OperationQueue> task_queue;
public: 
    Machine(int op, bool st) : operation_num(op), state(st){}
 
    void SetStartTime(int currentTime) {
        task_queue.front().start = currentTime;
    }
 
    int GetStartTime() {
        return task_queue.front().start;
    }
 
    void SetPriority()
    {
        if (!task_queue.empty()) {
            for (int i = 0; i < task_queue.size(); i++) {
                //task_queue.at(i).priority = (task_queue.at(i).time + task_queue.at(i).wait) / 2;
                task_queue.at(i).priority = task_queue.at(i).time;
            }
        }
    }
    
    bool EmptyQueue() {
        bool temp = task_queue.empty();
        return temp;
    }
 
    int GetOperationNr() { //???
        return operation_num;
    }
 
    void SortQueue()
    {
        if (!task_queue.empty()) {
            sort(task_queue.begin(), task_queue.end(), [](const OperationQueue& a, const OperationQueue& b) {
                return a.priority < b.priority;
            });
        }
    }
 
    void AddOperation(int task, int time) {
        OperationQueue nq;
        nq.task_num = task;
        nq.time = time;
        nq.wait = 0;
        nq.priority = NULL;
 
        task_queue.push_back(nq);
    }
 
    void GetInfoAboutMachine() {
        cout << "state : " << state << " | operation number : " << operation_num << endl;
    }
 
    void GetInfoAboutQueue() {
        for (size_t i = 0; i < task_queue.size(); i++)
        {
            cout << "index : " << i << " | task number : "<< task_queue.at(i).task_num << " | time : "<< task_queue.at(i).time << " | priority : " << task_queue.at(i).priority << " | start : " << task_queue.at(i).start << endl;
        }
    }
 
    int GetTime() {
        return  task_queue.front().time;
    }
 
    void ReduceTime(int min) {
        task_queue.front().time -= min;
    }
 
    bool GetState() {
        return state;
    }
 
    void SetState(bool st) {
        state = st;
    }
 
    int GetFree() {
        int nr;
        state = true;
        nr = task_queue.front().task_num;
        task_queue.pop_front();
 
        return nr;
    }
    
};
 
 
int main()
{
    bool tasks_state = true;
    int num_machines;
    int num_tasks;
    int current_time = 0;
 
    deque<deque<Operation>> tasks;
    deque<Machine> machines;
 
    cin >> num_tasks >> num_machines;
 
    //num_tasks = 3; 
    //num_machines = 3;
    //int array_temp[5][6] = { {0, 2, 1, 2, 2, 2 }, {1, 2, 0, 4, 2, 1}, {2, 4, 1, 2, 0, 1},{ 1, 4, 2, 2, 0, 4 }};
 
    //вводим данные для deque->deque->structure
    for (unsigned i = 0; i < num_tasks; i++) {
        deque<Operation> temp_deque;
        tasks.push_back(temp_deque);
 
        for (int j = 0; j < num_machines; j++) { 
            Operation temp_structure;
 
            //temp_structure.num = array_temp[i][j];
            //temp_structure.time = array_temp[i][j+1];
 
            cin >> temp_structure.num >> temp_structure.time;
            tasks.at(i).push_back(temp_structure);
        }
    }
 
    //создаем список машин deque->Machine class
    for (int j = 0; j < num_machines; j++) {
        Machine temp_machine(j, false);
        machines.push_back(temp_machine);
    }
 
    //Заполняем очереди в машинах
    for (unsigned i = 0; i < num_tasks; i++) {
        for (int j = 0; j < num_machines; j++) {
            if (tasks.at(i).front().num == j){
                machines.at(j).AddOperation(i, tasks.at(i).front().time);
                tasks.at(i).pop_front();
                break;
            }
        }
    }
 
    //Отсортируем перед началом
    for (int j = 0; j < num_machines; j++) {
        machines.at(j).SetPriority();
        machines.at(j).SortQueue();
 
        //Установим текущее время, для начала операций
        machines.at(j).SetStartTime(current_time);
    }
 
    deque<deque<int>> results;
    results.resize(tasks.size());
 
    while (tasks_state)
    {
 
        int min_time = 100000;
        int machine_index;
 
        //Если машина свободна то добавляю задачу в очередь, сортирую и устанавливаю время. 
        for (int i = 0; i < tasks.size(); i++) {
            for (unsigned j = 0; j < machines.size(); j++) {
                if (machines.at(j).GetState()) {
                    if (!(tasks.at(i).empty()) && (tasks.at(i).front().num == machines.at(j).GetOperationNr())) {
                        machines.at(j).AddOperation(i, tasks.at(i).front().time);
                        machines.at(j).SetState(false);
                        tasks.at(i).pop_front();
 
                        machines.at(j).SetPriority();
                        machines.at(j).SortQueue();
 
                        machines.at(j).SetStartTime(current_time);
                        break;
                    }
                }
            }
        }
 
        //Проверка есть ли в tasks задачи
        tasks_state = false;
        for (int i = 0; i < tasks.size(); i++) {
            if (!(tasks.at(i).empty())) {
                tasks_state = true;
            }
        }
 
        //Нахожу минимальный квант времени 
        for (int i = 0; i < machines.size(); i++) {
            if (!machines.at(i).EmptyQueue()) {
                if ((machines.at(i).GetTime() < min_time)) {
 
                    machine_index = i;
                    min_time = machines.at(i).GetTime();
                }
            }
        }
 
        //Обновляю время работы в каждой машине - т.е. просто отнимаю мин время 
        for (size_t i = 0; i < machines.size(); i++) {
            if (!machines.at(i).EmptyQueue()) {
                machines.at(i).ReduceTime(min_time);
                //Проверяю закончила ли машина работу над операцией 
                if (machines.at(i).GetTime() == 0) {
                    int del_start_time = machines.at(i).GetStartTime();
                    int del_index = machines.at(i).GetFree();
                    //в machine добавить время и записать в результирующий массив
                    results.at(del_index).push_back(del_start_time);
                    machines.at(i).SetState(true);
                }
            }
        }
 
        current_time += min_time;
    }
 
    for (size_t i = 0; i < results.size(); i++) {
        for (size_t j = 0; j < results.at(i).size(); j++) {
            cout << results.at(i).at(j) << " ";
        }
        cout << endl;
    }
 
    system("pause");
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
13.01.2018, 17:23
Ответы с готовыми решениями:

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

Посоветуйте как реализовать алгоритм
Алгоритм шифрования: bres = (bsrc ROL (i mod M)), где bsrc – i-ый байт кодируемого файла, bres – i-ый байт в результирующем файле,...

Посоветуйте!Как реализовать идею?
Есть база данных.Она является почтовой.В ней есть агент, который собирает инфу об учреждении из другой БД. (Название учреждения, адрес и...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
13.01.2018, 17:23
Помогаю со студенческими работами здесь

Посоветуйте как реализовать разметку
Пример приложения ВК Есть может библиотеки готовые? В идеале нужно что то типа https://github.com/mikepenz/MaterialDrawer но не...

Как лучше реализовать форум? (посоветуйте)
Всем привет! Ув. форумчане))) Подскажите как правильнее сделать... Имею интернет магазин товаров хоз товаров и товаров для сада,...

Что лучше: www.site.com/shop или shop.site.com?
Какой вариант лучше: www.site.com/shop или shop.site.com? В каком случае легче раскрутить? Какие особенности?

Как реализовать или посоветуйте другой FTP server
OC: Debian использую vsftpd захожу под логином 'root', надо создать еще логин для ftp с паролем и доступом только к определенной...

Увеличение/уменьшение проецируемого изображения, как правильно реализовать. Посоветуйте
Доброго времени суток! Есть лазерная указка, с насадкой. Если посветить на стену например с 2-3 метров- видим рисунок. если отойти еще...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
Контроль уникальности заводского номера - вариант №2
Maks 24.03.2026
В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++
8Observer8 24.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip
Жизнь в неопределённости
kumehtar 23.03.2026
Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения.
anaschu 23.03.2026
geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .
Контроль уникальности заводского номера - вариант №1
Maks 23.03.2026
Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .
Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения
anaschu 22.03.2026
e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git
Программный отбор элементов справочника по группе
Maks 22.03.2026
Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru