Будні автоматизації або «мені потрібна програмка для 3D упаковки»

  Автоматизація вітчизняних підприємств, якій доводитися займатися, це потрібна і високооплачувана, але досить нервова робота. Виручає гумор. Наприклад, при спілкуванні з вимогливим клієнтом можна згадати анекдот: «Тримаючись руками за стіну, на ногах ледве стоїть мужик. До нього пристає дитина: "Ну, тату, будь ласка, зроби мені кораблик!", Тато відповідає: "Ага! — Зараз все кину і піду робити тобі кораблик! ". Про один такий зроблений для клієнта "кораблик" і хочеться розповісти. Сподіваюся, спільне занурення в теплу лампове (тобто клієнтоорієнтованої) програмування доставить Вам позитивні емоції, та й завдання попалася цікава. Попливли?
 
 image
 
Почалося все з листа клієнта, в якому говорилося що великий мережевий ритейлер Х (всі його знають) зажадав, щоб відвантаження на його адресу здійснювалися на палетах, а в коробах заданого розміру. Тому менеджеру, який курирує даного клієнта, потрібно "програмка", яка за складом різнорозмірних упаковок в замовленні визначить необхідну кількість коробів і роздрукує пакувальні листи. Лист супроводжувалося проханням не затягувати вирішення питання, оскільки момент переходу на нову систему відвантажень ось-ось настане, а штрафні санкції можуть коштувати більше, ніж новий автомобіль генерального. Вартість автомобіля була відома, так як «Феррарі» значилася в списку основних засобів. Тому завдання знехотя (всього одне робоче місце з майже пари сотень) була взята в роботу і поставлена ​​на контроль. Хоча більш масових завдань в той момент було море: тільки-тільки запущено свежеразработанное ПО для терміналів збору даних на складі сировини, в режимі ошпареної кішки велася розробка програми для перекладу торгових представників з КПК на планшети, відладжувалася система реєстрації та контролю переміщень палет з готовою продукцією тощо.
 
Побіжний аналіз показав, що завдання "container loading" є NP-повною. Пояснити це клієнтові, який регулярно примхливим голосом набивався з питанням "коли ж буде моя програмка", ми не могли і не намагалися. А Ви спробуйте сказати симпатичній дівчині-менеджеру по роботі з клієнтами, що її завдання якась там повна. Про що вона в першу чергу подумає? І які у вас після цього шанси? Загалом, наївна віра наших клієнтів в безмежні можливості комп'ютерів і всемогутність програмістів зіграла в той раз з нами черговий жарт. Але треба було викручуватися і ми це зробили.
 
Щоб пояснити наведене далі рішення потрібно мати на увазі ще одну обставину. Фреймворк, з яким ми працюємо, заснований на скриптовій мовою. Хоча мова досить гнучкий і обвешен за принципом різдвяної ялинки всякими хлопавками і брязкальцями, включаючи навіть методи математичної статистики, він не дуже добре пристосований для задач з об'ємними обчисленнями. Звичайний цикл у нас виконується набагато довше, ніж в компільованих мовою. Тому прості, але масові обчислення буває зручніше робити на стороні сервера безпосередньо на рівні СУБД. Для роботи з базою даних у нас використовується мова, дуже схожий на T-SQL. Тому не сумніваюся, що наведений далі код буде всім зрозумілий.
 
Ідея рішення полягає в тому, щоб розкреслити дно короба на маленькі клітинки, отримати в таблиці всі можливі варіанти розташування кожної упаковки у вузлах сітки з урахуванням можливих обертань цієї упаковки, зафіксувати вибір кращого конкретного розташування одній з упаковок, а потім скорегувати таблицю рішень, "піднявши "можливі розташування інших, що залишилися упаковок на висоту зафіксованої упаковки, якщо їх розміщення перетинаються.
 
Загалом, ви зрозуміли, що ми використовували "жадібний" алгоритм. До речі, мабуть, побачивши це необережно написане слово в листі обліку робочого часу, головний бухгалтер потім довго бурчала і не хотіла підписувати рахунок за перероблені години.
 
Розмір клітин сітки, взагалі кажучи, має дорівнювати найбільшою загальною делителю усіх боків упаковок, але в нашому конкретному випадку розмірний ряд сторін упаковок був відомий: сторона клітини була взята рівною одному сантиметру.
 
Отже, спочатку отримуємо таблицю чисел від 0 до 255 каскадним зведенням у ступінь таблиці з 0 і 1.
 
 
SELECT 0 AS x
	INTO R1                                 
UNION
SELECT 1;

SELECT L.x + 2 * H.x AS x
	INTO R2
	FROM R1 AS L, R1 AS H;

SELECT L.x + 2 * H.x AS x
	INTO R4
	FROM R2 AS L, R2 AS H;

SELECT L.x + 2 * H.x AS x
	INTO R8
	FROM R4 AS L, R4 AS H;

 
Потім отримуємо таблицю всіх можливих обертань упаковок. До речі, цікава задача, щоб перевірити своє знання TSQL. Можливо, це новий паззл SQL для Joe Celko
 
 
SELECT id, CASE x WHEN 0 THEN d0 WHEN 1 THEN d1 WHEN 2 THEN d2 END AS dx, x
	INTO Scan
	FROM Items, R2
	WHERE x < 3;
 
SELECT DISTINCT B0.id, B0.dx AS d0, B1.dx AS d1, B2.dx AS d2
	INTO Spin
	FROM Scan AS B0
		JOIN Scan AS B1 ON B0.id = B1.id
		JOIN Scan AS B2 ON B0.id = B2.id
	WHERE NOT(B0.x = B1.x OR B0.x = B2.x OR B1.x = B2.x);

Нарешті, инициализируем таблицю рішень, множачи координати сітки на таблицю обертань.
 
 
SELECT FromLeft.x AS d0l, FromBack.x AS d1l, FromLeft.x + d0 AS d0h, FromBack.x + d1 AS d1h, 0 AS d2l, d2 AS d2h, 0 AS v, d0 * d1 AS s, id
	INTO Vista
	FROM R8 AS FromLeft, R8 AS FromBack, Spin
	WHERE FromLeft.x + d0 < = &Width AND FromBack.x + d1 < = &Depth AND d2 < = &Height;

 
Тепер виконуємо цикл:
 
Для вибору кращого варіанту використовується наступний запит.
 
 
SELECT TOP 1 id, d0l, d1l, d2l, d0h, d1h, d2 
	FROM Vista 
	WHERE d2l + d2 < = &Height 
	ORDER BY s * d2l - v, s * d2 DESC, d2l + d2, d0l, d1l, d0h;

 
Тобто на черговому кроці для укладання в короб за цим правилом вибирається упаковка, мінімально закриває під собою незайнятий об'єм. При рівних умовах закривається порожнечі вибирається упаковка максимального обсягу, мінімально піднімає верхній рівень упаковок в коробі, з самим лівим краєм, з найдальших краєм, з найдальших фронтом. Втім, правило легко змінити, змінивши порядок сортування.
 
Зміна таблиці рішень з урахуванням того, що деякий місце в коробі стає зайнятим, робиться так:
 
 
SELECT Vi.d0l, Vi.d1l
, ISNULL(CASE WHEN It.d2l + It.d2 > Vi.d2l THEN It.d2l + It.d2 END, Vi.d2l) AS d2l
, Vi.d0h, Vi.d1h, Vi.d2
, Vi.v + ISNULL((CASE WHEN It.d1l < Vi.d1l THEN It.d1l ELSE Vi.d1l END - CASE	WHEN It.d0l > Vi.d0l THEN It.d0l ELSE Vi.d0l END) 
* (CASE	WHEN It.d1h < Vi.d1h THEN It.d1h ELSE Vi.d1h END - CASE	WHEN It.d1l > Vi.d1l THEN It.d1l ELSE Vi.d1l END) * It.d2, 0) AS v
, Vi.s,	Vi.id
	FROM Vista AS Vi
		LEFT JOIN Items AS It
		ON (Vi.d1l < = It.d1l AND It.d1l < Vi.d1h OR It.d1l < = Vi.d1l AND Vi.d1l < It.d1h)
			AND (Vi.d0l < = It.d0l AND It.d0l < Vi.d0h OR It.d0l < = Vi.d0l AND Vi.d0l < It.d0h)
	WHERE Vi.id <> &id AND It.id = &id;

 
Ну а якщо немає жодної нерозміщення упаковки, яка піднімає рівень менш, ніж висота короба, вважаємо короб заповненим і инициализируем таблицю рішень заново для наступного короба.
 
Ось, загалом-то, і все.
 
Обмірковувалося рішення досить довго. Але не за комп'ютером, а в поїздках від фабрики клієнта за містом до центрального офісу. Думати за кермом досить зручно — складні рішення фільтруються самі собою. На саме програмування пішло приблизно половина дня.
 
Нижче наведено скріншот пакувального листа, використаного при налагодженні.
 
 Ð¡ÐºÑ€Ð¸Ð½ÑˆÐ¾Ñ‚ упаковочного листа
 
Справжній пакувальний лист виглядає досить нудно: графіка 2,5 Д пакувальникам виявилася не потрібною. Власне результат роботи представляє собою просто ще одну друковану форму, подключаемую до замовлення. Працює на типових замовленнях даного конкретного клієнта досить швидко.
 
Загалом, клієнт в особі дівчини-менеджера залишився задоволений. Правда, не так, щоб дуже. А ось чому? Навряд чи її могла розладнати інструкція до програмці, в якій говорилося, що вона працює тільки з товстим клієнтом у звичайних формах (це була десята редакція). Адже ми всі знаємо, що більшість наших клієнтів ніколи не відкривають інструкцій. Загалом, розгадка думок окремих користувачів це вам не «container loading», а дійсно нерозв'язна проблема.
 
Цікаво, що на тому ж проекті була ще заявка заступника начальника відділу постачання, який витрачав багато часу, підбираючи план випуску продукції, щоб найкращим чином розпорядитися наявними сировиною. Але це вже інша історія.
 
PS: Тут все правда і нічого не вигадано — колеги не дадуть збрехати. Причому найбільш глибоке враження чомусь залишилося у тих, кого я підвозив тоді на своїй синій імпрезі. Всі запам'ятали число 200, але це були аж ніяк не досягнуті відсотки утилізації обсягу короба.
Ось такий парадокс психології!
 
© ildarovich
  
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.