ALNS heuristic for the single-machine scheduling problem with family setup times and resource constraints

• Grant number: 21/02899-7
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: July 01, 2021
• End date: June 30, 2022
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Marcelo Seido Nagano
• Grantee: Larissa Satie Hayakawa
• Host Institution: Escola de Engenharia de São Carlos (EESC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

This project adresses the single-machine scheduling problem to minimize total tardiness. In this case, each job has a completion time, a due date and a certain amount of resource. At any time, the total resource consumption must not outnumber the total resource supply. Otherwise, the machine has to be idle until the total resource supply is sufficient to process the job. That said, this project proposes the aplication of the Adaptative Large Neighborhood Search (ALNS) heuristic. The heuristic will be implemented and its performance will be compared with the best heuristic from the literature.Keywords: single-machine; family setup times; resource constraints; total tardiness. (AU)