Heuristic methods for the single-machine scheduling problem with periodical resource constraints

Bruno de Athayde Prata (), Levi Ribeiro Abreu () and José Ytalo Ferreira Lima ()
Additional contact information
Bruno de Athayde Prata: Federal University of Ceará
Levi Ribeiro Abreu: Federal University of Ceará
José Ytalo Ferreira Lima: Federal University of Ceará

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2021, vol. 29, issue 2, No 12, 524-546

Abstract: Abstract In the last years, researchers have been paying special attention to scheduling problems with scarce resource consumption and periodic maintenance activities with a view to the adoption of more realistic assumptions. This paper aims at presenting heuristics to a single-machine scheduling environment with periodical resource constraints. In this new variant of the single-machine scheduling problem, in each production period, there are resource consumption constraints. To the best of our knowledge, the proposed variant has not been addressed in the revised literature. An integer linear programming model is presented based on a bin packing formulation taking two packing constraints into consideration. The objective function adopted is makespan minimization, and relative deviation is used as a performance criterion. Since the problem under study is NP-hard, heuristic algorithms are proposed to obtain high-quality solutions in acceptable computational times. Eighteen constructive heuristics, two local search heuristics, and a hybrid matheuristics, based on the size reduction and simulated annealing algorithms, have been presented. The extensive computational experience carried out shows that the proposed local search algorithms, as well as the proposed matheuristics, are promising tools to solve large-sized instances.

Keywords: Production sequencing; Scarce resources; Makespan; Size reduction; 90B35; 90C59 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-020-00574-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:29:y:2021:i:2:d:10.1007_s11750-020-00574-x

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-020-00574-x

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().