article

A Fully Polynomial Approximation Scheme for the Weighted Earliness-Tardiness Problem

Authors:

Mikhail Y. Kovalyov,

Wieslaw KubiakAuthors Info & Claims

Operations Research, Volume 47, Issue 5

Pages 757 - 761

https://doi.org/10.1287/opre.47.5.757

Published: 01 May 1999 Publication History

Abstract

A fully polynomial approximation scheme for the problem of scheduling n jobs on a single machine to minimize total weighted earliness and tardiness is presented. A new technique is used to develop the scheme. The main feature of this technique is that it recursively computes lower and upper bounds on the value of partial optimal solutions. Therefore, the scheme does not require any prior knowledge of lower and upper bounds on the value of a complete optimal solution. This distinguishes it from all the existing approximation schemes.

Cited By

View all

Li SChen RFeng QJiao C(2022)Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejectionJournal of Combinatorial Optimization10.1007/s10878-019-00429-738:3(957-971)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s10878-019-00429-7
Ji MTang XZhang XCheng T(2016)Machine scheduling with deteriorating jobs and DeJong's learning effectComputers and Industrial Engineering10.1016/j.cie.2015.10.01591:C(42-47)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.cie.2015.10.015
Ji MYang QYao DCheng T(2015)Single-machine batch scheduling of linear deteriorating jobsTheoretical Computer Science10.1016/j.tcs.2015.02.025580:C(36-49)Online publication date: 17-May-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.02.025
Show More Cited By

A Fully Polynomial Approximation Scheme for the Weighted Earliness-Tardiness Problem

Recommendations

A 1.47-approximation algorithm for a preemptive single-machine scheduling problem

In this note, we give a 1.47-approximation algorithm for the preemptive scheduling of jobs with release dates on a single machine so as to minimize the weighted sum of job completion times; this problem is denoted by 1|r"j,pmtn|@?"jw"jC"j in the ...
A fully polynomial approximation scheme for the total tardiness problem

A fully polynomial approximation scheme is presented for the problem of sequencing jobs for processing by a single machine so as to minimize total tardiness. This result is obtained by modifying the author's pseudopolynomial algorithm for the same ...
A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work

This paper studies approximation algorithms for the problem of nonpreemptively scheduling n jobs on a single machine to minimize total weighted late work, where the late work for a job is the amount of processing of this job that is performed after its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Operations Research Volume 47, Issue 5

May 1999

141 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 1999

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li SChen RFeng QJiao C(2022)Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejectionJournal of Combinatorial Optimization10.1007/s10878-019-00429-738:3(957-971)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s10878-019-00429-7
Ji MTang XZhang XCheng T(2016)Machine scheduling with deteriorating jobs and DeJong's learning effectComputers and Industrial Engineering10.1016/j.cie.2015.10.01591:C(42-47)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.cie.2015.10.015
Ji MYang QYao DCheng T(2015)Single-machine batch scheduling of linear deteriorating jobsTheoretical Computer Science10.1016/j.tcs.2015.02.025580:C(36-49)Online publication date: 17-May-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.02.025
Ji MYao DYang QCheng T(2015)Machine scheduling with DeJong's learning effectComputers and Industrial Engineering10.1016/j.cie.2014.12.00980:C(195-200)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.cie.2014.12.009
Zhao CHsu CCheng SYin YWu C(2014)Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobsApplied Mathematics and Computation10.1016/j.amc.2014.09.095248:C(503-510)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.amc.2014.09.095
Ji MHsu CYang D(2013)Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity considerationJournal of Combinatorial Optimization10.1007/s10878-011-9415-126:3(437-447)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1007/s10878-011-9415-1
Liu MZheng FChu CZhang J(2012)An FPTAS for uniform machine scheduling to minimize makespan with linear deteriorationJournal of Combinatorial Optimization10.1007/s10878-010-9364-023:4(483-492)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1007/s10878-010-9364-0
Zhao CJi MTang H(2011)Parallel-machine scheduling with an availability constraintComputers and Industrial Engineering10.1016/j.cie.2011.05.00961:3(778-781)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.cie.2011.05.009
Kacem IKellerer H(2011)Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release datesJournal of Scheduling10.1007/s10951-009-0146-414:3(257-265)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s10951-009-0146-4
Kellerer HStrusevich V(2010)Fully Polynomial Approximation Schemes for a Symmetric Quadratic Knapsack Problem and its Scheduling ApplicationsAlgorithmica10.5555/3118226.311846557:4(769-795)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.5555/3118226.3118465
Show More Cited By

Abstract

Cited By

Recommendations

A 1.47-approximation algorithm for a preemptive single-machine scheduling problem

A fully polynomial approximation scheme for the total tardiness problem

A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations