Тема
"Приближённые алгоритмы"

1. Имеется n деталей и m станков. Каждая деталь характеризуется 3 параметрами: временем доставки, временем обработки и временем доставки на склад. Станок обрабатывает любую деталь сразу, все станки одинаковы. Определить порядок обработки деталей на станках, когда все детали будут на складе за минимальное время.
2. Имеется n деталей и m станков. Каждая деталь характеризуется 2 параметрами: временем доставки, временем обработки. Станок обрабатывает любую деталь сразу, все станки одинаковы. Определить порядок обработки деталей на станках, когда все детали будут обработаны за минимальное время.
3. Имеется n деталей и 2m станков двух типов. Деталь обрабатывается в две стадии: сначала на станке первого типа, затем на станке второго типа. Каждая деталь характеризуется 2 параметрами: временем обработки на станке первого типа и временем обработки на станке второго типа. Станок обрабатывает любую деталь сразу, станков разных типов одинаково. Определить порядок обработки деталей на станках, когда все детали будут обработаны за минимальное время.
4. Имеется n работ и m работников. Каждая работа характеризуется длительностью её исполнения работником (все работники одинаковы). Необходимо так распределить работы среди работников, чтобы минимально загруженный работник был загружен как можно больше.
5. Имеется n работ. Каждая работа характеризуется длительностью её исполнения работником (все работники одинаковы). Необходимо так распределить работы среди работников, чтобы каждый работник был загружен не менее времени X, при этом количество работников было занято как можно больше.
6. Имеется n работ и m работников. Каждая работа характеризуется длительностью её исполнения каждым работником. Необходимо так распределить работы среди работников, чтобы максимально загруженный работник был загружен как можно меньше.
7. Имеется n программ, m одинаковых процессоров и 1 сервер. Каждая программа характеризуется временем скачивания данных с сервера и временем выполнения её на процессоре. Необходимо так организовать выполнение программ на процессорах, при котором время завершения последней программы минимально.
8. Имеется n камней и m машин в очереди. Камни характеризуются массой, машины грузоподъемностью. Необходимо определить порядок загрузки, при которой минимизируется количество используемых машин.
9. Имеется n предметов и много контейнеров. Каждый предмет характеризуется массой и объемом. Грузоподъемность и объем контейнера известны. Необходимо упаковать предметы в минимальное число контейнеров.
10. Имеется n городов, каждый из которых является либо потребителем, либо поставщиком продукции. Число X(k) характеризует его спрос (отрицательное) или предложение (положительное). Необходимо определить минимальную грузоподъемность машины и маршрут, которая может объехать все города по разу и удовлетворить потребности. (сумма спроса = сумме предложения).
11. Имеется n программ, m одинаковых процессоров и 1 сервер. Каждая программа характеризуется временем скачивания данных с сервера и временем выполнения её на процессоре. Необходимо так организовать выполнение программ на процессорах, при котором время завершения последней программы минимально. Распределение программ по процессорам известно заранее.
12. Решить задачу коммивояжера на плоскости, если положение городов задаются координатами.
13. Решить задачу Штейнера на плоскости с прямоугольной метрикой.
14. Дано n векторов, сумма которых равна 0. Необходимо определить такой порядок суммирования, так чтобы все частичные суммы попадали в шар минимального радиуса.
15. Имеется m станков и детали, о которых известна только информация о суммарном времени их обработки. Каждая деталь характеризуется временем обработки. Станок обрабатывает любую деталь сразу, все станки одинаковы. При этом детали поступают по очереди, причем нет никакой информации о следующей детали и их количестве. Поступившая деталь должна быть сразу назначена на один из станков, и это назначение не может быть изменено позже. Определить порядок обработки деталей на станках, когда все детали будут обработаны за минимальное время.
16. Имеется n работ и m работников. Каждая работа характеризуется длительностью её исполнения работником (все работники одинаковы). Для каждого работника известен список работ, которые он может выполнять. Необходимо так распределить работы среди работников, чтобы минимизировать время выполнения последней работы.
17. Имеется n работ и m работников. Каждая работа характеризуется длительностью её исполнения работником единичной производительности. Для каждого работника известна его производительность. Необходимо так распределить работы среди работников, чтобы минимизировать время выполнения последней работы.
18. Имеется n работ. Каждая работа характеризуется 2 параметрами: временем подготовки и временем выполнения. Имеется 1 исполнитель, который выполняет работы. Подготовкой он не занимается. Качество его работы характеризуется штрафом, который для каждой работы равен разности между временем начала работы и временем её возможного раннего начала. Определить порядок работ, при котором суммарный штраф всех работ минимален.
19. Имеется n деталей, m станков одного типа и 1 станок второго типа. Деталь обрабатывается в две стадии: сначала на станке первого типа, затем на станке второго типа. Каждая деталь характеризуется 2 параметрами: временем обработки на станке первого типа и временем обработки на станке второго типа. Станок обрабатывает любую деталь сразу. Определить порядок обработки деталей на станках, когда все детали будут обработаны за минимальное время.
20. Решить задачу коммивояжера на плоскости, если положение городов задаются координатами. Расстояние считается в прямоугольной метрике.
21. В городе имеется несколько маршрутов транспорта. Известны стоимости проезда между станциями. Необходимо поделить город на К зон, установить стоимость в каждой зоне и стоимость проезда между зонами, чтобы максимальное изменение цена проезда между станциями было минимально.
22. Имеется n деталей, m последовательных станков. Для каждой работы известно время выполнения на каждом станке. Необходимо определить порядок обработки деталей, при котором последняя деталь обработается как можно раньше.
23. Имеется n деталей и m станков. Для каждой работы известно время выполнения на каждом станке и последовательность прохождения станков каждой деталью. Необходимо определить порядок обработки деталей, при котором последняя деталь обработается как можно раньше.
24. Имеется n деталей, m последовательных станков. Для каждой работы известно время выполнения на каждом станке и частичный порядок предшествования деталей. Необходимо определить порядок обработки деталей, при котором последняя деталь обработается как можно раньше.
25. Имеется n городов и m машин. Необходимо объехать каждый город ровно 1 раз, используя некоторое число машин, чтобы стоимость проезда была минимальной. Города задаются координатами точек на плоскости.