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)

• 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
• On fixed-parameter tractability and approximability of NP optimization problems
• An introduction to the analysis of approximation algorithms
• Exact algorithms and approximation schemes for proportionate flow shop scheduling with step-deteriorating processing times
• Single-machine primary-secondary scheduling with total tardiness being the primary criterion
• An approximation algorithm for scheduling two parallel machines with capacity constraints.
• On scheduling multiple two-stage flowshops
• Scheduling with an orthogonal resource constraint
• A hybrid heuristic approach to minimize number of tardy jobs in group technology systems
• Load balancing of temporary tasks in the \(\ell _{p}\) norm
• Server cloud scheduling
• Scheduling parallel tasks with individual deadlines
• Bicriterion scheduling with a negotiable common due window and resource-dependent processing times
• Approximation schemes for subset-sums ratio problems
• On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks
• On maximal and minimal triangular planar graphs: an optimization approach
• Heuristic methods and applications: A categorized survey
• Impact of deadline intervals on behavior of solutions to the random sequencing jobs with deadlines problem
• Optimal delivery time quotation in supply chains to minimize tardiness and delivery costs
• Title not available (Why is that?)
• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
• General approximation algorithms for some arithmetical combinatorial problems
• Fast fully polynomial approximation schemes for minimizing completion time variance
• State aggregation in dynamic programming - an application to scheduling of independent jobs on parallel processors
• Anarchy in the UJ: coordination mechanisms for minimizing the number of late jobs
• Single-machine scheduling with an external resource
• Approximate Deadline-Scheduling with Precedence Constraints
• Minimizing functions of infeasibilities in a two-machine flow shop
• Random sequencing jobs with deadlines problem: Growth of the optimal solution values
• Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
• Worst-case analysis for on-line service policies
• Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
• Complexities of four problems on two-agent scheduling
• A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
• Worst-case analysis of LPT scheduling on a small number of non-identical processors
• NP-Complete operations research problems and approximation algorithms
• Two‐agent scheduling with linear resource‐dependent processing times
• A state-of-the-art survey on multi-scenario scheduling
• Title not available (Why is that?)
• Online learning for min-max discrete problems
• Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries
• Maximizing Throughput in Flow Shop Real-Time Scheduling
• Approximating the least core value and least core of cooperative games with supermodular costs
• Scheduling and fixed-parameter tractability
• Multiprofessor scheduling
• Exponential size neighborhoods for makespan minimization scheduling
• Recursive functions on the plane and FPTASs for production planning and scheduling problems with two facilities
• New results for scheduling to minimize tardiness on one machine with rejection and related problems
• Minimizing labor requirements in a periodic vehicle loading problem
• Knapsack with variable weights satisfying linear constraints
• A new approach for bicriteria partitioning problem
• Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates
• Serial batching to minimize the weighted number of tardy jobs
• A PTAS for the average weighted completion time problem on unrelated machines.
• Improving the solution complexity of the scheduling problem with deadlines: a general technique
• A note on sequencing jobs with deadlines problem
• The bound coverage problem by aligned disks in \(L_1\) metric
• On the integration of theoretical single-objective scheduling results for multi-objective problems
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan
• Parameterized multi-scenario single-machine scheduling problems
• Minimizing the weighted number of tardy jobs on a single machine: strongly correlated instances
• Parallel machine batching and scheduling with deadlines
• Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems
• Single-machine scheduling with autonomous and induced learning to minimize total weighted number of tardy jobs
• Branch distance optimization of structured programs
• Single-machine time-dependent scheduling with proportional and delivery times
• Job Tardiness in Unequal Parallel Processor Systems
• A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops
• Performance of service policies in a specialized service system with parallel servers
• Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans
• A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops
• Heuristic scheduling of parallel machines with sequence-dependent set-up times
• Single-machine batch scheduling with job processing time compatibility
• Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains
• Multi-machine scheduling with interval constrained position-dependent processing times
• A general lower bound for the makespan problem
• Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines
• 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

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)