Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

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

  • Original Paper
  • Published:
Operational Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Chung-Yee L (1991) Parallel machines scheduling with non-simultaneous machine available time. Discrete Appl Math 30(1):53–61

    Article  Google Scholar 

  • Chung-Yee L (1996) Machine scheduling with an availability constraint. J Global Optim 9(3):395–416

    Google Scholar 

  • Coffman Jr, Graham RL (1972) Optimal scheduling for two-processor systems. Acta Inform 1(3):200–213

    Article  Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK, Rinnooy KAHG (1979) Optimization and approximation in deterministic sequencing and scheduling. Ann Discrete Math 5(1):287–326

    Article  Google Scholar 

  • Guinand F, Trystram D (2000) Scheduling UET trees with communication delays on two processors. Rairo Oper Res 34(2):131–144

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Panneerselvam R (2006) Simple heuristic to minimize total tardiness in a single machine scheduling problem. Int J Adv Manuf Technol 30(7):722–726

    Article  Google Scholar 

  • Ponnambalam SG, Aravindan P, Rajesh SV (2000) A tabu search algorithm for job shop scheduling. Int J Adv Manuf Technol 16(10):765–771

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Veltman B, Lageweg BJ, Lenstra JK (1990) Multiprocessor scheduling with communication delays. Parallel Comput 16(2):173–182

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Khaoula Ben Abdellafou.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12351-018-0432-z

Keywords

Navigation