Heuristic algorithms for scheduling intrees on m machines with non-availability constraints

Khaoula Ben Abdellafou (), Hatem Hadda and Ouajdi Korbaa
Additional contact information
Khaoula Ben Abdellafou: University of Sousse
Hatem Hadda: Université de Tunis El Manar
Ouajdi Korbaa: University of Sousse

Operational Research, 2021, vol. 21, issue 1, No 2, 55-71

Abstract: Abstract Many real-world scheduling problems are solved to obtain optimal solutions in terms of processing time, cost, and quality as optimization objectives. Parallel computing systems promise higher performance for computationally intensive applications. Since programs for parallel systems consist of tasks that can be executed simultaneously, task scheduling becomes crucial for the performance of these applications. This problem has also its own application in the industry where machines may not always be available due to machine breakdowns or preventive maintenance during the scheduling period. Given dependence constraints between tasks and limited resources available for execution, optimal task scheduling is considered as an NP-hard problem. Thus, the development of heuristic methods that provide high-quality solutions with computational efficiency are the motivating aspects for the development of this research. This paper proposes a heuristic for scheduling n tasks subject to intree-precedence constraints on m identical machines subject to non-availability constraints. We also present a tabu search implementation and identify a polynomial algorithm to schedule a chain in the same environment. The tabu search algorithm along with the heuristic are compared via simulation to a proposed lower bound.

Keywords: Scheduling; Non-availability; Heuristic; Tabu search; Makespan; Intree. (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-018-0432-z 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:operea:v:21:y:2021:i:1:d:10.1007_s12351-018-0432-z

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-018-0432-z

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().