An iterative algorithm for scheduling UET tasks with due dates and release times.
type: Item
instance of: scholarly article
title: An iterative algorithm for scheduling UET tasks with due dates and release times.
zbMATH Open document ID: 1059.90078
DOI: 10.1016/S0377-2217(02)00770-1
author: Yakov Zinder
published in: European Journal of Operational Research
publication date: 2003-07-30T00:00:00Z
review text: A classical scheduling problem involving Unit Execution Time (UET) tasks is considered. A new polynominal-time iterative algorithm is presented for scheduling UET task system with parallel identical processors, precedence constraints, release times, and the criterion of maximum lateness. For the maximum lateness and makespan problems the algorithm allows to achieve the performance guarantees previously known only for the problems without release times.
reviewed by: Jacek Blazewicz
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 1957046
zbMATH Keywords: Scheduling
zbMATH Keywords: parallel processors
zbMATH Keywords: precedence constraints
zbMATH Keywords: maximum lateness
zbMATH Keywords: worst-case analysis
MaRDI profile type: Publication
cites work: A New Insight into the Coffman–Graham Algorithm
cites work: Q2734595
cites work: Q4247460
cites work: Scheduling Tasks with Nonuniform Deadlines on Two Processors
cites work: Two-Processor Scheduling with Start-Times and Deadlines
cites work: Worst Case Analysis of Two Scheduling Algorithms
cites work: NP-complete scheduling problems
cites work: PREEMPTIVE SCHEDULING ON PARALLEL PROCESSORS WITH DUE DATES
cites work: An iterative algorithm for scheduling unit-times tasks with precedence constraints to minimise the maximum lateness
description: scientific article; zbMATH DE number 1957046