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

DOI10.1016/j.orl.2014.05.009zbMath1408.90143OpenAlexW1974081328MaRDI QIDQ1785249

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

zbMATH Keywords

complexityschedulingpenalty function

Mathematics Subject Classification ID

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

Related Items (2)

The TV advertisements scheduling problem ⋮ For the airplane refueling problem local precedence implies global precedence

Cites Work

• Unnamed Item
• Unnamed Item
• Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
• Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• FPTAS for half-products minimization with scheduling applications
• Scheduling around a small common due date
• Scheduling about a given common due date to minimize mean squared deviation of completion times
• Completion time variance minimization on a single machine is difficult
• An improved precedence rule for single machine sequencing problems with quadratic penalty
• Single machine scheduling to minimize total weighted tardiness
• An exact algorithm to minimize mean squared deviation of job completion times about a common due date
• Minimization of Half-Products
• On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
• Minimizing Total Tardiness on One Machine is NP-Hard
• MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK
• Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Dual Techniques for Scheduling on a Machine with Varying Speed
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Algorithms for minclique scheduling problems

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