производственный план, практическая задача Опции

[мисс_граффити]

Доброго времени суток.
Сразу скажу, что задача не олимпиадная, а сугубо практическая.
Поэтому объяснение может получиться немножко сумбурным.

Итак. Есть фабрика по производству металлических дверей. Двери могут быть разных цветов (красные, коричневые, зеленые... ). Время производства одной двери от цвета не зависит.
Производственная мощность - скажем, 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 сент).

Есть идеи по формализации алгоритма?

[Unconnected]

Наверное сначала нужно выполнить план (ближайший заказ - добавлено), а потом смотреть, какие двери самые востребованные на следующие дни по плану (каких больше), и на остаток мощности красить их. Если после этого ещё осталась мощность - красить вторые по востребованности, и т.д. Только я не очень понял, на что здесь влияет условие про время смены краски..

Сообщение отредактировано: Unconnected - 14.09.2010 20:37

[мисс_граффити]

Unconnected, что значит "сначала выполнить план"? смысл в том, что его составить надо...
условие про время смены краски... ну если бы время было нулевое, можно было бы просто идти по заказам.
сделать 2 красные, 3 синие, потом 5 зеленых и еще 2 красные.
в реальных условиях если краску придется менять 1 раз - за день получится не 40 дверей, а 35. Если два раза - 30. и так далее.

[Unconnected]

что значит "сначала выполнить план"?

Извиняюсь, хотел сказать "выполнить ближайший заказ".

Сообщение отредактировано: Unconnected - 14.09.2010 20:38

[TarasBer]

Первое, что в голову пришло, насчёт оптимальности не знаю.

В течение дня логично сначала tR времени делать двери текущего цвета (оставшегося со вчера), потом tG какого-нибудь другого и tB третьего. Вопрос лишь в том, как выбрать tR, tG, tB.

Смотрим, какие есть недоделанные на сегодня, пусть кол-во несделанных дверей 3 цветов равно R, G, B (случай, когда одно из них нулевое, то есть краску можно не менять, не рассматриваю).
Смотрим, сколько времени на них понадобится с учётом 2 смен краски (tR1, tG1, tB1).
Оставшееся время делим в пропорции, соответствующей спросу на цвет, получив числа (tR2, tG2, tB2).
Тогда tR = tR1+tR2 итд.