В общем, была задача на оптимизацию плана работ: есть набор заказов, и в каждом N тасков. Таски могут зависеть друг от друга или нет, имеют длительность и тип. Ещё есть M работников, каждый из которых может выполнять таски только определённых типов, причём, у каждого своя скорость.
Если все таски в заказе выполнены, фирма получает сколько-то денег. У заказа есть дедлайн, за просрочку штраф (за каждый день просрочки), который вычитается из цены заказа. И ещё фирма тратит деньги за каждый день своей работы независимо от того, как загружены её сотрудники (то есть просто платит зарплаты по сути). Ещё важен учёт праздников и выходных.
Нужно заработать на определённом наборе заказов и работников как можно больше денег. Полный текст задачи и код программы проверки есть в репозитории. Эта задача является изменённым заказом, который мы с напарником решали в реальной жизни: оптимизация работы печатных станков для типографии. Правда, тогда и мы справились так себе, и заказчик в итоге сначала захотел всё вручную сам делать, а потом и вовсе похоронил проект при смене директора.
!!! Не читайте дальше, если хотите сначала попробовать решить самостоятельно, потому что я сейчас опишу эффективные подходы и результаты.
________________________________________
Так вот. Мы с другим экспертом Андреем сразу сели и написали разные варианты, чтобы задать шкалу, по которой будем оценивать решения команд. За пару часов я собрал примитивный жадный алгоритм, который сортировал заказы по прибыльности и укладывал в сетку кое-как, это дало нам нижнюю оценку. Мой алгоритм заработал ~75 млн виртуальных рублей, мы решили для оценки поставить нижней границей 40 млн. То есть всё, что ещё ниже, оценивалось в ноль баллов за качество оптимизации.
Затем Андрей закрылся дома на три дня и вышел на свет со сложным жадным алгоритмом, который очень хитро сортировал заказы и очень хитро укладывал их в сетку, попутно выбирая разные способы этой укладки в зависимости от конкретного заказа. Это позволило заработать ~275 млн рублей. Мы сделали верхней границей для оценки 280 млн.
К сожалению, в итоге только две команды из десяти прошли нижнюю границу, заработав, соответственно, ~91 и ~105 млн. К верхней границе не приблизился никто. И у четырёх команд алгоритм вообще не смог уложить без нарушений задачи в сетку (то есть, например, произвольно менял длительности, накладывал задачи друг на друга, давал одному работнику две задачи в один момент и так далее). Важной ошибкой команд, на мой взгляд, являлся тот факт, что никто не воспользовался возможностью запустить алгоритм на несколько минут и дать ему поработать. По условиям задания, можно было тянуть до 5 минут на одну оптимизацию, но по факту решения команд отрабатывали за единицы и десятки секунд.
На самом конкурсе, пока команды работали, я решил попробовать сделать быстрое (по времени написания) но эффективное решение. Сначала попробовал жадную сортировку + доведение до лучшего варианта методом имитации отжига. В качестве нового состояния я просто менял местами заказы целиком. Этот вариант работал пару минут и дал мне около ~200 млн дохода. К слову, команда-лидер использовала такой же подход, просто не докрутила число итераций и температуру.
Ну и потом я взял готовую либу по реализации классической генетики с особями и скрещиванием. Особью был массив с приоритетами заказов (которые конечно же нужно было аккуратно уложить чистым алгоритмом). Тип скрещивания: scattered. Всего 15 поколений по 20 особей, и это за минуту-полторы давало ~230-240 млн. Считаю, что для конкурса это самый лучший выбор: пишется одним человеком за день и даёт почти максимум, при этом легко настраивается на нужную длительность работы, легко параллелится.
Ну а потом уже дома я посидел и накодил свой вариант сложного жадного с плавающим окном перебора отсортированных заказов и плавающей же укладкой по работникам. Такая штука за две минуты зарабатывает ~281 млн. Но за три дня в условиях стресса я бы такое не сделал, скорее всего.
#dev
We all are one.
The sun, the moon and the earth are one (once),
But in the time they all seperated,
Being and living far away,
But they all are one.
We born on different places,
We raised in different cities,
We studied in different institutions,
But we all are on one stage. i.e,, Life.
Our handwriting may be different
But the alphabet are one,
Pens may be different,
But the ink is same,
Books may be different,
But the knowledge is eternal.
We all are separated ,
by life,
by paths,
By careers,
But our hearts are together,
and We all are one.
Our tastes,
our preferences,
our perspectives,
our thinking,
May be different but,
We all are one.
S NAVEEN
#poetry#SN#review
Seperation lives
The life of human started from seperation,
Separation from the ocean,
Separation from the species, and
Separation from the womb of mother.
Nature is separated,
Oceans are separated,
Continents are separated, and so,
The nations emerged seperately.
Separation is the birth of new life,
Separation leads to innovation,
Separation is the worse, but
Separation is the nature.
When two persons seperates,
The heart brokes, and
Mind resides in despair, and
Life teaches the valuable lessons.
Even the origin of universe,
Started from the separation,
From one to one and another,
Separation is an unending process.
Separation begins with despair and,
End with hope.
Separation is natural and,
Separation is permanent.
PS: ignore grammatical mistakes
S NAVEEN
10-07-2022
#poetry#SN#review
Deadly hunger
I have seen that one person begged,
Other person insulted his fellow being,
And the other person cried for his condition.
I have seen people selling their body,
I have seen one died, and
Other inviting the death.
I have seen one in misery,
Other fighting to end the misery,
And other mentally broke down in it.
I have seen the starvation of children,
I have seen men working hard, and
The old seeking for help.
I have seen false promises of politicians,
Flop ideas of business men,
Which told to end hunger and poverty.
Hunger, a six letters word,
Running the world with ruthless,
Where it has no permanent end.
S NAVEEN
23-06-2022
#poetry#SN#review
These nights
I hope sleep find its way,
Before my thoughts destroy me,
Exhausted feelings and emotions will make,
These nights more scary.
There was a nights in moon light,
where we are sleeping peacefully,
Why this artificial lights making,
These nights more terrible.
In the war of mind and heart,
Sleep is just a pawn,
Where heart and mind will never win the war,but
These nights witness as spectators.
S NAVEEN
#poetry#SN#review
Sky...
You are the blue,
You are the light,
You are the carrier of clouds.
You have been witnessing the war,
You have been witnessing the peace,
You have been witnessing the love,
You have been witnessing the world. (From Alpha)
You have seen the tragedy,
You have seen the lives,
You have seen the nature,
You are the meaning of eternal.
You took the poison,
You took the pollution,
Yet, you never changed your colour. (like politicians)
You are the miniature of the oceans.
You are the floating blue ocean and
wonder of the universe.
S NAVEEN
#poetry#SN#review
On Long distance relationship.
Distance is just a word,
When two hearts beat together,
Kilometres and miles are just measurements,
When two souls turns into one.
There may be lack of communication,
But two minds will think the same.
Distance and lack of communication is;
Just for those, who thinks they are separate,
Not for those, who thinks they are together.
Love never thinks it way in impossibilities,
It always find it ways in possibilities.
S. NAVEEN
#poetry#SN#review
Eternal Love
I just opened the eyes,
Aloud tears filled the room,
That's the first time that,
I saw true form of love,
My Mother.
She hugged and kissed me,
With happiness and tears in her eyes,
That's the selfless love.
I have never seen 'her' before,
But I felt her touch in womb,
Her hands touched me,
Her womb protected me.
I have seen her and cried,
Her gentleness in heart,
Her intangible love,
Is the pinnacle in the whole world.
S NAVEEN
#poetry#SN#review