Production scheduling with sequence-dependent setups and job release times

This paper studies a shortterm production scheduling problem inspired from reallife manufacturing systems consisting on the scheduling a set of jobs (production orders) on both a single machine and identical parallel machines with the objective of minimizing the makespan or maximum completion time of all jobs. Jobs are subject to release dates and there are sequence-dependent machine setup times. Since this problem is known to be strongly NP-hard even for the single machine case, this paper proposes a heuristic algorithm to solve it. The algorithm uses a strategy of random generation of various execution sequences, and then selects the best of such schedules. Experiments are performed using random-generated data and show that the heuristic performs very well compared against the optimal solution and lower bounds, and requiring short computational time.

• Autores: Montoya Torres, Jairo Rafael; Soto Ferrari, Milton Rene; González Solano, Fernando
• Tipo de recurso: Article of journal
• Fecha de publicación: 2010
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/37605
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/37605; http://bdigital.unal.edu.co/27689/
• Palabra clave: Scheduling; sequence-dependent setup times; release dates; randomness; heuristic.
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional