Scheduling with Cadence Constraints



               Department of Systems Engineering and Engineering Management

                       The Chinese University of Hong Kong


Date: Friday Sep 30, 2022, 12:30 pm - 1:30 pm HK time

Venue: Zoom

Title: Scheduling with Cadence Constraints

Speaker: Prof. Anand Subramanian, Department of Computer Systems, Universidade Federal da Paraíba, Brazil


Zoom link:

Meeting ID: 923 4642 7338

Passcode: 298476



This work aims at supporting the assembly operations of a multinational automotive company. Their Brazilian lines are scheduled so the cars that are more demanding in workforce are not in close proximity one to another. More precisely, two policies are defined: one imposes that no more than a fixed number of cars from given sets can be scheduled contiguously, and the other enforces how far apart cars from given sets have to be one from another. Both policies implicitly define a punctuation in the sequence, and the managers in the company refer to the values associated with these policies as cadences. The goal is to sequence the maximum number of consecutive cars, without violating any policy. The company currently assembles these lines manually, which takes hours and still violates the policies an average of 16.08 times per instance. Our approach to solve this problem presents two integer programming formulations, as well as a formulation that finds a feasible schedule for a given number of cars, should there be any such, which in turn is embedded within binary and iterative search algorithms. Both algorithms are further enhanced by combinatorial and heuristic bounds. The latter can be described as an effective iterated local search algorithm with ad hoc strategies to quickly explore the neighborhoods and diversify the solutions. Extensive computational results showed that the binary search algorithm with heuristic and combinatorial bounds and the iterative algorithm with a combinatorial upper bound performed best, solving the instances reflecting the company's needs optimally within seconds.


Anand Subramanian is an Associate Professor at the Department of Computer Systems at Universidade Federal da Paraíba (UFPB), Brazil. He received his B.Sc. degree in Mechanical Production Engineering from UFPB in 2006 and his M.Sc. degree in Production Engineering in 2008 from the same institution. He obtained his D.Sc. degree in Computing in 2012 from the Universidade Federal Fluminense (UFF), Brazil. His D.Sc. thesis was selected as one of the top 3 of Brazil in the field of Computer Science, and he received an Honorable Mention award from the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES), on behalf of the Brazilian Ministry of Education. His research interests are mainly related to developing heuristic, exact and hybrid algorithms for combinatorial optimization problems. Anand is an author of more than 50 articles published in highly-ranked international journals. In 2016 he received the highly cited research award from Elsevier for the paper “A hybrid algorithm for a class of vehicle routing problems” published in Computers & Operations Research (C&OR). He has been a member of the Editorial Advisory Board of C&OR since 2019. Anand is the organizer and host of the "Subject to" podcast.

Everyone is welcome to attend the talk!

SEEM-5201 Website:


Friday, September 30, 2022 - 12:30 to 13:30