Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays
F. Abasian
, Mohammad Ranjbar
, M. Salari
, , M. Khatami
2014, Applied Mathematical Modelling, 38(15-16), pp.3975-3986
Scheduling
Parallel processors
Communication delay
Branch-and-bound algorithm
Abstract
This paper addresses a certain type of scheduling problem that arises when a parallel computation is to be executed on a set of identical parallel processors. It is assumed that if two precedence-related tasks are processed on two different processors, due to the information transferring, there will be a task-dependent communication delay between them. For each task, a processing time, a due date and a weight is given while the goal is to minimize the total weighted late work. An integer linear mathematical programming model and a branch-and-bound algorithm have been developed for the proposed problem. Comparing the results obtained by the proposed branch-and-bound algorithm with those obtained by CPLEX, indicates the effectiveness of the method.