Algorithms for Scheduling Independent Tasks

DOI10.1145/321921.321934zbMATH Open0326.68024OpenAlexW2067297441MaRDI QIDQ4091444FDOQ4091444

Authors: Sartaj Sahni 

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321921.321934

Recommendations

• A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
• APPROXIMATE AND EXACT ALGORITHMS FOR SCHEDULING INDEPENDENT TASKS ON UNRELATED PROCESSORS
• Scheduling independent multiprocessor tasks
• scientific article; zbMATH DE number 3883925
• Scheduling independent multiprocessor tasks

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Algorithms in computer science (68W99)

Cited In (only showing first 100 items - show all)

• Minimizing the total weighted completion time of fully parallel jobs with integer parallel units
• Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs
• The just-in-time scheduling problem in a flow-shop scheduling system
• Improved algorithms for single machine scheduling with release dates and rejections
• A new approach to the learning effect: Beyond the learning curve restrictions
• Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs
• The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost
• Scheduling to minimize the maximum total completion time per machine
• A survey on offline scheduling with rejection
• Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
• Efficient partitioning of sequences
• Isomorphic scheduling problems
• A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
• On bilevel machine scheduling problems
• A new branch and bound algorithm for minimizing the weighted number of tardy jobs
• Unrelated parallel machine scheduling with new criteria: complexity and models
• Title not available (Why is that?)
• FPTAS for half-products minimization with scheduling applications
• Combination of parallel machine scheduling and vertex cover
• Theoretical comparisons of search strategies in branch-and-bound algorithms
• Tight bounds for the identical parallel machine scheduling problem
• Approximation algorithms for scheduling unrelated parallel machines
• Feasibility of scheduling lot sizes of two frequencies on one machine
• Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals
• Fast approximation algorithm for job sequencing with deadlines
• Approximation algorithms for scheduling with reservations
• A state-of-the-art review of parallel-machine scheduling research
• Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
• Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains
• Scheduling fully parallel jobs with integer parallel units
• Designing PTASs for MIN-SUM scheduling problems
• Structure preserving reductions among convex optimization problems
• Minimization of ordered, symmetric half-products
• A bicriteria approach to scheduling a single machine with job rejection and positional penalties
• An improved FPTAS for Restricted Shortest Path.
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Completeness in approximation classes
• Time-hierarchical scheduling. A worst case analysis of a hierarchical approach integrating planning and scheduling in an online problem
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• Approximation schemes for a class of subset selection problems
• Approximation algorithms for single machine scheduling with one unavailability period
• Uniform parallel-machine scheduling with time dependent processing times
• Improved approximation algorithm for the combination of parallel machine scheduling and vertex cover
• Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan
• Scheduling under linear constraints
• Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval
• Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
• Improved approximation algorithms for two-stage flowshops scheduling problem
• Two-machine flow-shop scheduling with rejection
• Minimizing the weighted number of tardy jobs on a single machine
• Minimizing the weighted number of tardy jobs on a single machine with release dates
• Optimal timing of a sequence of tasks with general completion costs
• Title not available (Why is that?)
• Two due date assignment problems in scheduling a single machine
• A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines
• A binary multiple knapsack model for single machine scheduling with machine unavailability
• A survey of single machine scheduling to minimize weighted number of tardy jobs
• Scheduling identical parallel machines to minimize total weighted completion time
• Matching based very large-scale neighborhoods for parallel machine scheduling
• Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel
• Single processor scheduling with job values depending on their completion times
• A new dynamic programming algorithm for the parallel machines total weighted completion time problem
• A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs
• Just-in-time scheduling with controllable processing times on parallel machines
• The complexity of finding Nash equilibria
• Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• Optimal due-date assignment and sequencing
• Scheduling proportionally deteriorating jobs in two-machine open shop with a non-bottleneck machine
• Using short-term memory to minimize the weighted number of late jobs on a single machine.
• Parallel approximation schemes for subset sum and knapsack problems
• Recent trends in combinatorial optimization
• An FPTAS for the parallel two-stage flowshop problem
• Single-machine scheduling with maintenance activities and rejection
• A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
• Improving the complexities of approximation algorithms for optimization problems
• Title not available (Why is that?)
• Scheduling parallel tasks with individual deadlines
• Approximation algorithms for scheduling a single machine to minimize total late work
• 0-1 Quadratic programming approach for optimum solutions of two scheduling problems
• Randomized priority algorithms
• Solving min-max shortest-path problems on a network
• Polynomial time approximation schemes and parameterized complexity
• Scheduling to minimize release-time resource consumption and tardiness penalties
• Single-machine serial-batch delivery scheduling with two competing agents and due date assignment
• Off-line temporary tasks assignment.
• Scheduling fully parallel jobs
• Maximizing set function formulation of two scheduling problems
• Approximation scheduling algorithms: a survey
• A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops
• Fast exact and approximate algorithms for \(k\)-partition and scheduling independent tasks
• Scheduling with machine conflicts
• A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
• Online real-time preemptive scheduling of jobs with deadlines on multiple machines
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• An efficient job scheduling algorithm in partitionable mesh connected systems
• Pareto‐optimization of three‐agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work
• Title not available (Why is that?)
• An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops
• Equivalence of some different maintenance activities in single-machine scheduling

This page was built for publication: Algorithms for Scheduling Independent Tasks

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