The solution algorithms for the multiprocessor scheduling with workspan criterion

In this paper, we consider multiprocessor scheduling problems, where each job (task) must be executed simultaneously by the specified number of processors, but the indices of the processors allotted to each job do not have to be contiguous (i.e., jobs can be fragmentable). Unlike other research in this domain, we analyse the problem under the workspan criterion, which is defined as the product of the maximum job completion time (makespan) and the number of used processors. Moreover, the job processing times can be described by non-increasing or non-decreasing functions dependent on the start times of jobs that model improvement (learning) or degradation (deteriorating), respectively. To solve the problems, we construct some polynomial time algorithms and analyse numerically their efficiency.

► The workspan criterion is defined. ► Polynomial time heuristics for multiprocessor scheduling problems with start time dependent job processing times are constructed. ► An extensive numerical analysis of the proposed algorithms is presented.