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)
|
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 |
Downloads
Downloads per month over past year