Читайте также:
|
Пусть есть два станка А и В. Каждая деталь должна быть обработана и на станке А (причем в первую очередь), и на станке В (во вторую очередь). Известны времена обработки каждой детали на каждом станке. Для разных деталей эти времена, вообще говоря, различные.
На каждом из станков можно обрабатывать только одну деталь. Процесс обработки деталей не может прерываться. Нужно определить вариант плана запуска деталей, при котором общее время их обработки будет минимальным.
Алгоритм решения этой задачи следующий.
1. На k-шаге для п — к + 1 деталей (к = 1, 2,..., п) просматриваются времена обработки деталей на каждом станке и среди них определяется минимум.
2. Если этот минимум относится к станку А, то соответствующая деталь занимает очередное место в начале плана запуска деталей и исключается из дальнейшего рассмотрения.
3. Если этот минимум относится к станку В, то соответствующая деталь занимает очередное место в конце плана запуска деталей и исключается из дальнейшего рассмотрения.
4. Если время обработки двух разных деталей на одном станке совпадает и это время меньше времени обработки на другом станке, то порядок обработки этих деталей произволен.
Пример. Есть два станка А и В. Каждая деталь должна быть обработана и на станке А (причем в первую очередь), и на станке В (во вторую очередь). Известны времена обработки каждой детали на каждом станке (в минутах). На каждом из станков можно обрабатывать только одну деталь. Процесс обработки деталей не может прерываться. Определим вариант плана запуска деталей, при котором общее время их обработки будет минимальным.
| Деталь | |||||
| Время обработки на станке А | |||||
| Время обработки на станке В |
Находим минимальное число во 2-й и 3-й строках. Это минимальное число равно 1 и показывает время обработки 4-й детали на станке А. Поэтому деталь 4 исключаем из дальнейшего рассмотрения, а план запуска деталей после 1-го шага имеет следующий вид: 4 -…
Получаем таблицу:
| Деталь | ||||
| Время обработки на станке А | ||||
| Время обработки на станке В |
Для полученной таблицы находим минимальное число во 2-й и 3-й строках. Таких чисел два: 2 (деталь 3, станок А) и 2 (деталь 2, станок В). Предпочтение отдается станку А. Поэтому деталь 3 исключаем из дальнейшего рассмотрения, а план запуска деталей после 2-го шага имеет следующий вид: 4 — 3 —... Получаем таблицу:
| Деталь | |||
| Время обработки на станке А | |||
| Время обработки на станке В |
После 3-го шага план запуска деталей имеет следующий вид: 4-3-...-2.
Окончательный вариант: 4 — 3 — 5—1 — 2. Найдем минимальное суммарное время обработки деталей на двух станках.
| Деталь | Станок А | Станок В | ||
| начало | окончание | начало | окончание | |
| 0+1 = 1 | 1 + 3 = 4 | |||
| 1 + 2 = 3 | 4 + 5 = 9 | |||
| 3 + 3 = 6 | 9 + 4= 13 | |||
| 6 + 3 = 9 | 13 + 5 = 18 | |||
| 9 + 4= 13 | 18 + 2 = 20 |
Поясним, как заполняется таблица. Время начала обработки очередной детали равно времени окончания обработки предыдущей детали на этом же станке. Время окончания обработки детали = время начала обработки детали + время обработки детали на соответствующем станке.
Минимальное суммарное время обработки деталей на двух станках равно 20 минут.
Задача. Есть два станка А и В. Каждая деталь должна быть обработана и на станке А (причем в первую очередь), и на станке В (во вторую очередь). Известны времена обработки каждой детали на каждом станке (в минутах). На каждом из станков можно обрабатывать только одну деталь. Процесс обработки деталей не может прерываться. Определить вариант плана запуска деталей, при котором общее время их обработки будет минимальным. Чему равно минимальное суммарное время обработки деталей на двух станках?
| № варианта | Деталь | |||||||||
| A | B | A | B | A | B | A | B | A | B | |
Дата добавления: 2015-07-11; просмотров: 545 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Ночные поллюции | | | МЕТОД ВЗВЕШИВАНИЯ |