Skip navigation

A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date

A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date

Kellerer, Hans, Rustogi, Kabir and Strusevich, Vitaly A. (2018) A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date. Omega. ISSN 0305-0483 (In Press) (doi:https://doi.org/10.1016/j.omega.2018.11.001)

[img] PDF (Author Accepted Manuscript)
22983 RUSTOGI_A_Fast_FPTAS_for_Single_Machine_Scheduling_Problem_2018.pdf - Accepted Version
Restricted to Registered users only until 3 May 2020.

Download (216kB) | Request a copy

Abstract

We address the single machine scheduling problem to minimize the total weighted earliness and tardiness about a nonrestrictive common due date. This is a basic problem with applications to the just-in-time manufacturing. The problem is linked to a Boolean programming problem with a quadratic objective function, known as the half-product. An approach to developing a fast fully polynomial-time approximation scheme (FPTAS) for the problem is identified and implemented. The running time matches the best known running time for an FPTAS for minimizing a half-product with no additive constant

Item Type: Article
Uncontrolled Keywords: Single machine scheduling; Earliness-Tardiness; Half-product problem; FPTAS
Subjects: Q Science > QA Mathematics
Faculty / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Mathematical Sciences
Last Modified: 12 Feb 2019 11:36
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
URI: http://gala.gre.ac.uk/id/eprint/22983

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics