МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА
Оптимальная раскраска φ смешанного графа G=(V,A,E) определяет расписание, которое минимизирует среднее время обслуживания n требований в системе job shop с единичными длительностями операций. Подграф (V,A,Æ) смешанного графа G представляет собой объединение путей, а подграф (V,Æ,E) – объединение кли...
Saved in:
| Format: | Article |
|---|---|
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2019-03-01
|
| Series: | Informatika |
| Online Access: | https://inf.grid.by/jour/article/view/836 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849771406816968704 |
|---|---|
| collection | DOAJ |
| description | Оптимальная раскраска φ смешанного графа G=(V,A,E) определяет расписание, которое минимизирует среднее время обслуживания n требований в системе job shop с единичными длительностями операций. Подграф (V,A,Æ) смешанного графа G представляет собой объединение путей, а подграф (V,Æ,E) – объединение клик. Разработан метод ветвей и границ для оптимальной раскраски смешанного графа G с критерием минимизации суммы номеров цветов, используемых для n требований. Проведен вычислительный эксперимент на ПЭВМ по построению оптимальной раскраски вершин смешанных графов порядка n £ 200, сгенерированных случайным образом. |
| format | Article |
| id | doaj-art-3db0acfb4e264980a768bb6ff91f8dba |
| institution | DOAJ |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2019-03-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-3db0acfb4e264980a768bb6ff91f8dba2025-08-20T03:02:37ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012019-03-0103(03)516798МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА01Объединенный институт проблем информатики НАН БеларусиОбъединенный институт проблем информатики НАН БеларусиОптимальная раскраска φ смешанного графа G=(V,A,E) определяет расписание, которое минимизирует среднее время обслуживания n требований в системе job shop с единичными длительностями операций. Подграф (V,A,Æ) смешанного графа G представляет собой объединение путей, а подграф (V,Æ,E) – объединение клик. Разработан метод ветвей и границ для оптимальной раскраски смешанного графа G с критерием минимизации суммы номеров цветов, используемых для n требований. Проведен вычислительный эксперимент на ПЭВМ по построению оптимальной раскраски вершин смешанных графов порядка n £ 200, сгенерированных случайным образом.https://inf.grid.by/jour/article/view/836 |
| spellingShingle | МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА Informatika |
| title | МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА |
| title_full | МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА |
| title_fullStr | МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА |
| title_full_unstemmed | МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА |
| title_short | МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА |
| title_sort | минимизация суммарного времени обслуживания требований с единичными длительностями операций на основе раскраски смешанного графа |
| url | https://inf.grid.by/jour/article/view/836 |