A Heuristic for a Scheduling Problem with Communication Delays | Zendy

Alix Munier | Zendy; JeanClaude König | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Heuristic for a Scheduling Problem with Communication Delays

Author(s) -

Alix Munier,

JeanClaude König

Publication year - 1997

Publication title -

operations research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 3.797

H-Index - 140

eISSN - 1526-5463

pISSN - 0030-364X

DOI - 10.1287/opre.45.1.145

Subject(s) - computer science , job shop scheduling , scheduling (production processes) , mathematical optimization , heuristic , distributed computing , parallel computing , computer network , mathematics , artificial intelligence , routing (electronic design automation)

This paper addresses a scheduling problem with interprocessor communication delays: the jobs and the communication delays are of unit length. The number of processors is unbounded. The aim is to minimize the makespan. We develop a new list scheduling heuristic and we prove that its worst-case relative performance is 4/3.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research