Правила форума
Доброго времени суток.
Сразу скажу, что задача не олимпиадная, а сугубо практическая.
Поэтому объяснение может получиться немножко сумбурным.
Итак. Есть фабрика по производству металлических дверей. Двери могут быть разных цветов (красные, коричневые, зеленые... ). Время производства одной двери от цвета не зависит.
Производственная мощность - скажем, 40 дверей в день.
Приходит клиент. Говорит: "Хочу 3 синих двери и 5 красных". Под него бронируется производственная мощность, ему сообщается дата готовности. Если он оплачивает счет (в течение 3 дней), его двери ставятся в план на производство.
Каждое утро формируется суточный план на следующий день (с учетом недовыполнения плана, отказов и т.п.).
Проблема в следующем: каждая смена цвета занимает примерно час (емкость освобождается от краски, промывается...). Соответственно, одноцветные двери надо группировать... Но при этом нарушать сроки - нельзя.
То есть, например, если я до завтра должна сделать 10 красных и 30 синих дверей, а до послезавтра 30 красных и 10 синих, я не могу сегодня сделать 40 красных, а завтра 40 синих - этим я срываю сроки поставки заказа первому клиенту. В итоге вместо одной смены краски придется делать две...
Т.е. имеем последовательность вида:
15 синих (до 20 сентября), 20 красных (20 сентября), 40 зеленых (21 сентября), 5 красных (25 сентября)...
Получить надо план:
19 сентября изготовить 25 красных и 15 синих
20 сентября 40 зеленых
а если бы на 25 сентября надо было не 5, а 10 красных - получилось бы иначе (они бы целиком не влезли в план на 19 сент).
Есть идеи по формализации алгоритма?
 производственный план, практическая задача |
