Heuristic methods for the single machine scheduling problem with different ready times and a common due date

Author(s)

Birgin, Ernesto G. ^[1] ; Ronconi, Debora P. ^[2]

Affiliation

^[1] Univ Sao Paulo, Inst Math & Stat, Dept Comp Sci, BR-05508090 Sao Paulo - Brazil

^[2] Univ Sao Paulo, Dept Prot Engn, EP USP, BR-05508900 Sao Paulo - Brazil

• Document type: Journal article
• Source: ENGINEERING OPTIMIZATION; v. 44, n. 10, p. 1197-1208, 2012.
• Web of Science Citations: 7

Abstract

The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs. (AU)

• FAPESP's process: 10/10133-0 - Cutting, packing, lot-sizing and scheduling problems and their integration in industrial and logistics settings
• Grantee: Reinaldo Morabito Neto
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 06/53768-0 - Computational methods of optimization
• Grantee: José Mário Martinez Perez
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 09/10241-0 - Theory and software in computational methods for optimization
• Grantee: Ernesto Julián Goldberg Birgin
• Support Opportunities: Regular Research Grants
• FAPESP's process: 06/03496-3 - Theory and practice of cutting and packing problems
• Grantee: Marcos Nereu Arenales
• Support Opportunities: Research Projects - Thematic Grants