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, 90:101992. ISSN 0305-0483 (doi:https://doi.org/10.1016/j.omega.2018.11.001)

[img]
Preview
PDF (Author Accepted Manuscript)
22983 RUSTOGI_A_Fast_FPTAS_for_Single_Machine_Scheduling_Problem_2018.pdf - Accepted Version

Download (216kB) | Preview

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 / School / Research Centre / Research Group: Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS)
Faculty of Engineering & Science
Last Modified: 04 Mar 2022 13:06
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