Deakin University

File(s) under permanent embargo

Just-in-time batch scheduling subject to batch size

conference contribution
posted on 2020-01-01, 00:00 authored by Sergey PolyakovskiySergey Polyakovskiy, Dhananjay ThiruvadyDhananjay Thiruvady, Rym M'Hallah
This paper considers single-machine just-in-time scheduling of jobs that may be grouped into batches subject to a constraint on batches' weights. A job has a weight, due date, and earliness and tardiness penalties per unit time. A batch's processing time is determined by its jobs. Each job inherits its batch's completion time. The objective is to minimize the weighted sum of earliness and tardiness penalties of all jobs. This problem is challenging: Jobs-to-batch assignment changes the batch's processing time; thus, affects the structure of the entire solution and most importantly of its cost components. This problem is an excellent benchmark for testing linkage learning techniques, which exploit a problem's structure. We propose a matheuristic LTGA, which integrates evolutionary algorithms with mixed-integer programming (MIP). It builds a linkage tree that extracts the dependency among decision variables of MIP solutions. We compare its performance to a state of the art matheuristic CMSA, which combines the learning component of an ant colony system (ACS) with MIP within a construct, solve, merge, and adapt framework. It uses knowledge extracted from ACS' ants to construct a restricted MIP, solves it efficiently, and feeds it back to ACS. Computational tests indicate that LTGA outperforms MIP solvers and CMSA.



Genetic and Evolutionary Computation. Conference (2020 : Cancun, Mexico)


228 - 235




Cancun, Mexico

Place of publication

New York, N.Y.

Start date


End date






Publication classification

E1 Full written paper - refereed

Title of proceedings

GECCO 2020 : Proceedings of the 2020 Genetic and Evolutionary Computation Conference