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.
Similar content being viewed by others
Abbreviations
- m :
-
Number of machines or processors
- n :
-
Number of tasks
- \(T_j\) :
-
Task number j in the graph
- \(p_j\) :
-
Processing time of \(T_j\)
- \(S_i\) :
-
Start time of the non-availability period of machine i
- \(F_i\) :
-
End time of the non-availability period of machine i
- \(\alpha\) :
-
Resumable factor
- \(Path(T_j)\) :
-
The sum of execution times of the nodes from \(T_j\) to the root
- leaf :
-
A leaf in an intree which is a task (or a node) that has no predecessors
References
Ben-Abdellafou K, Korbaa O (2016) A novel algorithm for scheduling intrees on two parallel machines with unavailabilities. In: IEEE international conference on systems man and cybernetics, Budapest, Hungary
Ben-Abdellafou K, Sanlaville E, Mahjoub A, Ouajdi K (2015) Scheduling UECT trees with communication delays on two processors with unavailabilities INCOM ottawa canada. IFAC-PapersOnLine 48(3):1790–1795
Ben-Abdellafou K, Hadda H, Korbaa O (2017) Heuristic for scheduling intrees on m machines with non-availability constraints. ISDA Intell Syst Des Appl 557:384–393
Chung-Yee L (1991) Parallel machines scheduling with non-simultaneous machine available time. Discrete Appl Math 30(1):53–61
Chung-Yee L (1996) Machine scheduling with an availability constraint. J Global Optim 9(3):395–416
Coffman Jr, Graham RL (1972) Optimal scheduling for two-processor systems. Acta Inform 1(3):200–213
Graham RL, Lawler EL, Lenstra JK, Rinnooy KAHG (1979) Optimization and approximation in deterministic sequencing and scheduling. Ann Discrete Math 5(1):287–326
Guinand F, Trystram D (2000) Scheduling UET trees with communication delays on two processors. Rairo Oper Res 34(2):131–144
Guinand F, Rapine C, Trystram D (1997) Worst-case analysis of algorithms for scheduling UECT trees on m processors. IEEE Trans Parall Distrib 8(10):1085–1086
Panneerselvam R (2006) Simple heuristic to minimize total tardiness in a single machine scheduling problem. Int J Adv Manuf Technol 30(7):722–726
Ponnambalam SG, Aravindan P, Rajesh SV (2000) A tabu search algorithm for job shop scheduling. Int J Adv Manuf Technol 16(10):765–771
Rapine C, Guinand F, Trystram D (1997) Worst case snalysis of Lawler’s algorithm for scheduling trees with communication delays. IEEE T Parall Distrib 8(10):1085–1086
Saad R (2007) Scheduling with communication delays. Technical report 754, LRI, University of Paris Sud, Paris, France
Safi A, Trystram D, Canon L (2014) A proactive approach for coping with uncertain resource availabilities on desktop grids. High Perform Comput Goa India 9(3):395–416
Sanlaville E, Mahjoub A, Guinand F (2014) Problmes d’ordonnancement sur machines parallles avec tches communicantes et indisponibilits (In french). ROADEF, Marseille, France
Theodora AV, Vwani PR, Thomas K, Lawler E (1996) Scheduling in and out forests in the presence of communication delays. IEEE Trans Parall Distrib 7(10):1065–1074
Veltman B, Lageweg BJ, Lenstra JK (1990) Multiprocessor scheduling with communication delays. Parallel Comput 16(2):173–182
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ben Abdellafou, K., Hadda, H. & Korbaa, O. Heuristic algorithms for scheduling intrees on m machines with non-availability constraints. Oper Res Int J 21, 55–71 (2021). https://doi.org/10.1007/s12351-018-0432-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12351-018-0432-z