Я выполняю административную работу в авиационной транспортной компании. Здесь строят контейнеры для самолетов и тому подобное. Одна из вещей, которую они хотят, чтобы я закодировал, — это сценарий оптимизации заказа, который ребята в зале могут использовать, чтобы получить максимальную отдачу от данного материала. Чтобы дать простой обзор: скажем, мы заказываем определенное количество балок по 10 метров за единицу. Нам нужны куски бруса 5х6м, 10х3,5м, 4х3м, которые получаются путем разрезания 10м на более мелкие части. Какое минимальное количество 10-метровых балок нам нужно заказать?
Есть некоторые параллели с проблемой планирования многопроцессорных заданий (один луч — это процессор, каждый фрагмент — задание), хотя здесь основное внимание уделяется минимизации времени, необходимого для выполнения всех заданий, а не минимизации количества процессоров, необходимых для выполнения всех заданий в рамках предварительной обработки. -установленное время. Проблема планирования многопроцессорных заданий находится в NP-complete, но мне интересно, мой вариант проблемы тоже. Кто-нибудь знает подобные проблемы и методы их решения?
