Heuristic algorithms for scheduling intrees on m machines with non-availability constraints
| Autor: | Hatem Hadda, Khaoula Ben Abdellafou, Ouajdi Korbaa |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
0209 industrial biotechnology
Numerical Analysis 021103 operations research Job shop scheduling Computer science Strategy and Management 0211 other engineering and technologies Computational intelligence 02 engineering and technology Management Science and Operations Research Preventive maintenance Upper and lower bounds Polynomial algorithm Tabu search Scheduling (computing) 020901 industrial engineering & automation Computational Theory and Mathematics Management of Technology and Innovation Modeling and Simulation Statistics Probability and Uncertainty Algorithm Limited resources |
| Zdroj: | Operational Research. 21:55-71 |
| ISSN: | 1866-1505 1109-2858 |
| DOI: | 10.1007/s12351-018-0432-z |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink