Dynamic programming approach to the single-machine sequencing problem with different due-dates

DOI10.1016/0898-1221(90)90001-ZMaRDI QIDQ913669zbMATH OpenOpenAlexFDO

Authors T. C. Edwin Cheng

Publication date 1990

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(90)90001-z

zbMATH Keywords

due-datesjob completion timesNP-completesum of absolute deviations

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Review text

A collection of jobs is to be processed in such a way that the sum of absolute deviations of job completion times about their respective due- dates is minimized. The problem is NP-complete and a dynamic programming approach is described which offers considerable computational savings over complete enumeration.

Recommendations

• An improved dynamic programming algorithm for the single-machine mean absolute deviation problem with a restrictive common due date
• Minimizing total completion time and total deviation of job completion times from a restrictive due-date
• Dynamic programming and decomposition approaches for the single machine total tardiness problem
• Publication:5750703
• A dynamic programming method for single machine scheduling

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• A Generalized Model of Optimal Due-Date Assignment by Linear Programming
• scientific article; zbMATH DE number 4059106 (Why is no real title available?)
• scientific article; zbMATH DE number 3401694 (Why is no real title available?)
• Minimizing mean absolute deviation of completion times about a common due date
• Minimizing the average deviation of job completion times about a common due date
• Minimizing the average deviation of job completion times about a common due-date: An extension
• Minimizing the sum of absolute lateness in single-machine and multimachine scheduling
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Single- and multiple-processor models for minimizing completion time variance
• Survey of scheduling research involving due date determination decisions
• The art and theory of dynamic programming

Cited in

(5)

• A dynamic programming method for single machine scheduling
• An improved dynamic programming algorithm for the single-machine mean absolute deviation problem with a restrictive common due date
• A new dynamic programming formulation of (n x m) flowshop sequencing problems with due dates
• scientific article; zbMATH DE number 4185378 (Why is no real title available?)
• Algorithm of sequential analysis of variants for minimization of the number of devices in scheduling problem with due date

This page was built for publication: Dynamic programming approach to the single-machine sequencing problem with different due-dates

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