Algorithms for minimizing maximum lateness with unit length tasks and resource constraints

DOI10.1016/0166-218X(93)90042-MMaRDI QIDQ1803669zbMATHDBLPWikidataFDO

Authors Jacek Blazewicz, Wieslaw Kubiak, Silvano Martello

Publication date 29 June 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

deterministic scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine
• An Algorithm for Minimizing the Range of Lateness on a Single Machine
• Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints
• Approximation algorithms for scheduling a single machine to minimize total late work
• An iterative algorithm for scheduling unit-times tasks with precedence constraints to minimise the maximum lateness
• Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• Minimizing the sum of absolute lateness in single-machine and multimachine scheduling
• Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty
• Approximation Algorithms for Scheduling Problems with Exact Delays

Cites work

• scientific article; zbMATH DE number 4095196 (Why is no real title available?)
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• A linear time algorithm for restricted bin packing and scheduling problems
• Algorithm 520: An Automatic Revised Simplex Method for Constrained Resource Network Scheduling [H]
• Bounds on list scheduling of UET tasks with restricted resource constraints
• Coffman-Graham scheduling of UET task systems with 0-1 resources
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Concurrent Task Systems
• Minimizing mean flow time with parallel processors and resource constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Preemptive Scheduling, Linear Programming and Network Flows
• Scheduling subject to resource constraints: Classification and complexity
• Scheduling tasks on two processors with deadlines and additional resources
• Simple algorithms for multiprocessor scheduling to meet deadlines
• Some new results in flow shop scheduling

Cited in

(6)

• Parallel machine scheduling with additional resources: notation, classification, models and solution methods
• LP rounding and combinatorial algorithms for minimizing active and busy time
• Production, maintenance and resource scheduling: a review
• Polynomial time algorithms for some minimum latency problems
• An iterative algorithm for scheduling unit-times tasks with precedence constraints to minimise the maximum lateness
• Algorithms and Data Structures

This page was built for publication: Algorithms for minimizing maximum lateness with unit length tasks and resource constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803669)