Algorithms for Scheduling Independent Tasks
From MaRDI portal
Publication:4091444
DOI10.1145/321921.321934zbMath0326.68024OpenAlexW2067297441MaRDI QIDQ4091444
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
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Deterministic scheduling theory in operations research (90B35) Algorithms in computer science (68W99)
Related Items
Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems, Exponential size neighborhoods for makespan minimization scheduling, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Approximate Deadline-Scheduling with Precedence Constraints, An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops, Approximation schemes for a class of subset selection problems, A new branch and bound algorithm for minimizing the weighted number of tardy jobs, On maximal and minimal triangular planar graphs: an optimization approach, 0-1 Quadratic programming approach for optimum solutions of two scheduling problems, Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs, On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks, Maximizing set function formulation of two scheduling problems, Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines, 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, Unrelated parallel machine scheduling with new criteria: complexity and models, A hybrid heuristic approach to minimize number of tardy jobs in group technology systems, A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops, Two‐agent scheduling with linear resource‐dependent processing times, Worst-case analysis of LPT scheduling on a small number of non-identical processors, Pareto‐optimization of three‐agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work, Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work, Improving the solution complexity of the scheduling problem with deadlines: A general technique, Equivalence of some different maintenance activities in single-machine scheduling, Single-machine scheduling with autonomous and induced learning to minimize total weighted number of tardy jobs, A state-of-the-art survey on multi-scenario scheduling, The bound coverage problem by aligned disks in \(L_1\) metric, A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem, Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines, Scheduling with machine conflicts, Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems, Approximating the least core value and least core of cooperative games with supermodular costs, Scheduling Fully Parallel Jobs with Integer Parallel Units, A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan, Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover, On the Integration of Theoretical Single-Objective Scheduling Results for Multi-objective Problems, Unnamed Item, Maximizing Throughput in Flow Shop Real-Time Scheduling, A new approach to the learning effect: Beyond the learning curve restrictions, A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines, Job Tardiness in Unequal Parallel Processor Systems, Designing PTASs for MIN-SUM scheduling problems, Minimizing labor requirements in a periodic vehicle loading problem, Unnamed Item, Server cloud scheduling, Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel, Load balancing of temporary tasks in the \(\ell _{p}\) norm, Improved approximation algorithms for two-stage flowshops scheduling problem, Approximation algorithms for scheduling with reservations, Heuristic scheduling of parallel machines with sequence-dependent set-up times, NP-Complete operations research problems and approximation algorithms, Unnamed Item, A Survey on Approximation Algorithms for Scheduling with Machine Unavailability, Theoretical comparisons of search strategies in branch-and-bound algorithms, Scheduling fully parallel jobs, SCHEDULING PROPORTIONALLY DETERIORATING JOBS IN TWO-MACHINE OPEN SHOP WITH A NON-BOTTLENECK MACHINE, Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem, Approximation scheduling algorithms: a survey, A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops, AN EFFICIENT JOB SCHEDULING ALGORITHM IN PARTITIONABLE MESH CONNECTED SYSTEMS, Solving min-max shortest-path problems on a network, Tight bounds for the identical parallel machine scheduling problem, Scheduling to minimize release-time resource consumption and tardiness penalties, Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier, Single-machine batch scheduling with job processing time compatibility, Scheduling with an orthogonal resource constraint, Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains, A new approach for bicriteria partitioning problem, An introduction to the analysis of approximation algorithms, Feasibility of scheduling lot sizes of two frequencies on one machine, New algorithms for minimizing the weighted number of tardy jobs on a single machine, Single-machine serial-batch delivery scheduling with two competing agents and due date assignment, Parallel approximation schemes for subset sum and knapsack problems, The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost, Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs, Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval, Anarchy in the UJ: coordination mechanisms for minimizing the number of late jobs, Time-hierarchical scheduling. A worst case analysis of a hierarchical approach integrating planning and scheduling in an online problem, Online real-time preemptive scheduling of jobs with deadlines on multiple machines, 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, Minimizing the weighted number of tardy jobs on a single machine with release dates, Improving the complexities of approximation algorithms for optimization problems, On fixed-parameter tractability and approximability of NP optimization problems, Complexities of four problems on two-agent scheduling, A binary multiple knapsack model for single machine scheduling with machine unavailability, Polynomial time approximation schemes and parameterized complexity, Two due date assignment problems in scheduling a single machine, State aggregation in dynamic programming - an application to scheduling of independent jobs on parallel processors, Online learning for min-max discrete problems, Approximation schemes for subset-sums ratio problems, A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs, A survey of single machine scheduling to minimize weighted number of tardy jobs, Single processor scheduling with job values depending on their completion times, Minimizing the total weighted completion time of fully parallel jobs with integer parallel units, Knapsack with variable weights satisfying linear constraints, A survey on offline scheduling with rejection, Multiprofessor scheduling, The symmetric quadratic knapsack problem: approximation and scheduling applications, Structure preserving reductions among convex optimization problems, Scheduling and fixed-parameter tractability, Matching based very large-scale neighborhoods for parallel machine scheduling, Parameterized multi-scenario single-machine scheduling problems, On bilevel machine scheduling problems, The just-in-time scheduling problem in a flow-shop scheduling system, An approximation algorithm for scheduling two parallel machines with capacity constraints., Fast approximation algorithm for job sequencing with deadlines, A bicriteria approach to scheduling a single machine with job rejection and positional penalties, Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates, General approximation algorithms for some arithmetical combinatorial problems, A state-of-the-art review of parallel-machine scheduling research, Uniform parallel-machine scheduling with time dependent processing times, Multi-machine scheduling with interval constrained position-dependent processing times, Single-machine scheduling with maintenance activities and rejection, Minimizing functions of infeasibilities in a two-machine flow shop, Performance of service policies in a specialized service system with parallel servers, Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals, On scheduling multiple two-stage flowshops, An FPTAS for the parallel two-stage flowshop problem, A note on sequencing jobs with deadlines problem, Approximation algorithms for scheduling a single machine to minimize total late work, Optimal due-date assignment and sequencing, A new dynamic programming algorithm for the parallel machines total weighted completion time problem, Fast exact and approximate algorithms for \(k\)-partition and scheduling independent tasks, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, Impact of deadline intervals on behavior of solutions to the random sequencing jobs with deadlines problem, Combination of parallel machine scheduling and vertex cover, Two-machine flow-shop scheduling with rejection, Bicriterion scheduling with a negotiable common due window and resource-dependent processing times, Minimization of ordered, symmetric half-products, Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan, Randomized priority algorithms, Just-in-time scheduling with controllable processing times on parallel machines, Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains, Worst-case analysis for on-line service policies, Optimal delivery time quotation in supply chains to minimize tardiness and delivery costs, Single-machine scheduling with an external resource, Scheduling to minimize the maximum total completion time per machine, Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval, FPTAS for half-products minimization with scheduling applications, Isomorphic scheduling problems, Using short-term memory to minimize the weighted number of late jobs on a single machine., A general lower bound for the makespan problem, Approximation algorithms for scheduling unrelated parallel machines, Approximation algorithms for single machine scheduling with one unavailability period, New results for scheduling to minimize tardiness on one machine with rejection and related problems, Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates, Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries, Heuristic methods and applications: A categorized survey, A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem, Parallel machine batching and scheduling with deadlines, Scheduling parallel tasks with individual deadlines, Minimizing the weighted number of tardy jobs on a single machine: strongly correlated instances, Recursive functions on the plane and FPTASs for production planning and scheduling problems with two facilities, Random sequencing jobs with deadlines problem: Growth of the optimal solution values, Recent trends in combinatorial optimization, A PTAS for the average weighted completion time problem on unrelated machines., An improved FPTAS for Restricted Shortest Path., Off-line temporary tasks assignment., A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems, Branch distance optimization of structured programs, Fast fully polynomial approximation schemes for minimizing completion time variance, Scheduling identical parallel machines to minimize total weighted completion time, A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective, Completeness in approximation classes, Minimizing the weighted number of tardy jobs on a single machine, Improved algorithms for single machine scheduling with release dates and rejections, An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
