Deakin University

File(s) under permanent embargo

Just-in-time batch scheduling problem with two-dimensional bin packing constraints

conference contribution
posted on 2017-01-01, 00:00 authored by Sergey PolyakovskiySergey Polyakovskiy, A Makarowsky, R M'Hallah
This paper introduces and approximately solves a multi-component problem where small rectangular items are produced from large rectangular bins via guillotine cuts. An item is characterized by its width, height, due date, and earliness and tardiness penalties per unit time. Each item induces a cost that is proportional to its earliness and tardiness. Items cut from the same bin form a batch, whose processing and completion times depend on its assigned items. The items of a batch have the completion time of their bin. The objective is to find a cutting plan that minimizes the weighted sum of earliness and tardiness penalties. We address this problem via a constraint programming (CP) based heuristic (CPH) and an agent based modelling heuristic (ABH). CPH is an impact-based search strategy, implemented in the general-purpose solver IBM CP Optimizer. ABH is constructive. It builds a solution through repeated negotiations between the set of agents representing the items and the set representing the bins. The agents cooperate to minimize the weighted earliness-tardiness penalties. The computational investigation shows that CPH outperforms ABH on small-sized instances while the opposite prevails for larger instances.



Genetic and evolutionary computation. Conference (2017 : Berlin, Germany)


321 - 328


The Association for Computing Machinery


Berlin, Germany

Place of publication

New York, N.Y.

Start date


End date






Publication classification

E Conference publication; E1.1 Full written paper - refereed

Copyright notice

2017, ACM.



Title of proceedings

GECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference