On the complexity of the single machine scheduling problem minimizing total weighted delay penalty

DOI10.1016/J.ORL.2014.05.009zbMATH Open1408.90143OpenAlexW1974081328MaRDI QIDQ1785249FDOQ1785249

Authors: Oscar C. Vásquez 

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2014.05.009

Recommendations

• Single-Machine Scheduling to Minimize a Function of Two or Three Maximum Cost Criteria
• scientific article; zbMATH DE number 40475
• Single machine total tardiness maximization problems: complexity and algorithms
• Publication:3478253
• Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty

zbMATH Keywords

complexityschedulingpenalty function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Title not available (Why is that?)
• FPTAS for half-products minimization with scheduling applications
• Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
• Minimization of half-products
• Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Algorithms for minclique scheduling problems
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Minimizing Total Tardiness on One Machine is NP-Hard
• Scheduling around a small common due date
• Single machine scheduling to minimize total weighted tardiness
• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• Title not available (Why is that?)
• Completion time variance minimization on a single machine is difficult
• Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
• The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution
• An improved precedence rule for single machine sequencing problems with quadratic penalty
• Dual techniques for scheduling on a machine with varying speed
• An exact algorithm to minimize mean squared deviation of job completion times about a common due date
• Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
• Scheduling about a given common due date to minimize mean squared deviation of completion times
• On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost

Cited In (4)

• The TV advertisements scheduling problem
• On the local dominance properties in single machine scheduling problems
• For the airplane refueling problem local precedence implies global precedence
• Algorithm for minimizing weighted earliness penalty in single-machine problem

This page was built for publication: On the complexity of the single machine scheduling problem minimizing total weighted delay penalty

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