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

• Record Type: Journal Article
• Authors: Kellerer, Hans; Rustogi, Kabir; Strusevich, Vitaly A.
• Is Part Of: Omega. Volume 90(2020)
• Publication Date: 2020-01
• Subjects: Single machine scheduling -- Earliness-Tardiness -- Half-product problem -- FPTAS; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2018.11.001
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: A single machine scheduling problem with JIT applications is studied. The total weighted earliness-tardiness about a large common due date is minimized. The problem is reduced to minimizing a special form of a half-product. A fully polynomial-time approximation scheme is presented. The running time is strongly polynomial, unlike previously known. 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.