Scheduling with Deadlines and Loss Functions

DOI10.1287/MNSC.6.1.1zbMath1047.90504OpenAlexW2058817479MaRDI QIDQ2768989

Robert McNaughton

Publication date: 22 October 2002

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/746ac1e37383b8f262dabcb1575fafde9b6a6389

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (only showing first 100 items - show all)

An introduction to parallelism in combinatorial optimization ⋮ Nonclairvoyant scheduling ⋮ Parametric analysis of the quality of single preemption schedules on three uniform parallel machines ⋮ Minimizing mean flow time with parallel processors and resource constraints ⋮ Batch scheduling with deadlines on parallel machines: an NP-hard case ⋮ Openshop and flowshop scheduling to minimize sum of completion times ⋮ A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions ⋮ Preemption in single machine earliness/tardiness scheduling ⋮ Quasi-partitioned scheduling: optimality and adaptation in multiprocessor real-time systems ⋮ Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays ⋮ A study of the cyclic scheduling problem on parallel processors ⋮ Nearly on line scheduling of preemptive independent tasks ⋮ List scheduling algorithms to minimize the makespan on identical parallel machines ⋮ Real-time scheduling of linear speedup parallel tasks ⋮ Total completion time minimization on multiple machines subject to machine availability and makespan constraints ⋮ On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: minimizing the makespan and delivery cost ⋮ Multi-rate fluid scheduling of mixed-criticality systems on multiprocessors ⋮ Rational preemptive scheduling ⋮ An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem ⋮ Parallel machine scheduling problem with preemptive jobs and transportation delay ⋮ ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times ⋮ New trends in machine scheduling ⋮ Approximate algorithms for the \(P\parallel C_{\max}\) problem ⋮ Models and complexity of multibin packing problems ⋮ Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints ⋮ Pre-emptive scheduling problems with controllable processing times ⋮ Scheduling parallel jobs to minimize the makespan ⋮ On a parallel machine scheduling problem with precedence constraints ⋮ A parametric maximum flow algorithm for bipartite graphs with applications ⋮ Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays ⋮ Is a unit-job shop not easier than identical parallel machines? ⋮ Redundant cumulative constraints to compute preemptive bounds ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Scheduling multiprocessor tasks on parallel processors with limited availability. ⋮ Single machine scheduling to minimize weighted sum of completion times with secondary criterion - A branch and bound approach ⋮ Online scheduling of unit jobs on three machines with rejection: a tight result ⋮ Energy-efficient real-time scheduling for two-type heterogeneous multiprocessors ⋮ Scheduling chained multiprocessor tasks onto large multiprocessor system ⋮ A survey of scheduling methods for multiprocessor systems ⋮ Search-based job shop scheduling and sequencing: Extensions to the search sequencing rule ⋮ {\textsc{DP-Fair}}: a unifying theory for optimal hard real-time multiprocessor scheduling ⋮ How useful are preemptive schedules? ⋮ An exact algorithm for the identical parallel machine scheduling problem. ⋮ Scheduling independent jobs with stochastic processing times and a common due date on parallel and identical machines ⋮ An optimal boundary fair scheduling algorithm for multiprocessor real-time systems ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ Scheduling open shops with parallel machines ⋮ Approximation results in parallel machines stochastic scheduling ⋮ Reducibility among single machine weighted completion time scheduling problems ⋮ A competitive two-agent scheduling problem on parallel machines with release dates and preemption ⋮ Semantic-aware optimization of user interface menus ⋮ Parallel machine covering with limited number of preemptions ⋮ Approximation schemes for packing with item fragmentation ⋮ Equivalence of mean flow time problems and mean absolute deviation problems ⋮ Robust algorithms for preemptive scheduling ⋮ Scheduling results applicable to decision-theoretic troubleshooting ⋮ Sequencing jobs on a single machine with a common due data and stochastic processing times ⋮ Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems ⋮ Minimizing the maximal ergonomic burden in intra-hospital patient transportation ⋮ T-L plane-based real-time scheduling for homogeneous multiprocessors ⋮ Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs ⋮ On the geometry, preemptions and complexity of multiprocessor and shop scheduling ⋮ A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes ⋮ Bin packing with fragmentable items: presentation and approximations ⋮ Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness ⋮ A study of scheduling problems with preemptions on multi-core computers with GPU accelerators ⋮ Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources ⋮ Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches ⋮ Parallel machine scheduling with speed-up resources ⋮ A heuristic for preemptive scheduling with set-up times ⋮ Complexity and approximation of an area packing problem ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ Scheduling on parallel machines with preemption and transportation delays ⋮ A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time ⋮ Scheduling unrelated parallel machines with optional machines and jobs selection ⋮ A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity ⋮ Scheduling two agents with controllable processing times ⋮ Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem ⋮ Minimizing mean weighted execution time loss on identical and uniform processors ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ Synchronous flow shop scheduling with pliable jobs ⋮ Packing resizable items with application to video delivery over wireless networks ⋮ A polynomial algorithm for an open shop problem with unit processing times and tree constraints ⋮ Preemptive scheduling with variable profile, precedence constraints and due dates ⋮ Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times ⋮ Preemptive online scheduling: Optimal algorithms for all speeds ⋮ Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard ⋮ Batch scheduling with deadlines on parallel machines ⋮ Maximizing the production rate in simple assembly line balancing -- A branch and bound procedure ⋮ Scheduling multiprocessor tasks with chain constraints ⋮ Parallel machine scheduling with splitting jobs ⋮ The single-machine total tardiness scheduling problem: review and extensions ⋮ Optimal virtual cluster-based multiprocessor scheduling ⋮ Minimizing average completion time in the presence of release dates ⋮ Minimizing the number of machines for minimum length schedules ⋮ Resource augmentation in load balancing. ⋮ A heuristic for the single machine tardiness problem ⋮ Linear and quadratic algorithms for scheduling chains and opposite chains ⋮ Linear programming models for load balancing ⋮ An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems

This page was built for publication: Scheduling with Deadlines and Loss Functions