Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem

1982/04/01 by S. S. Panwalkar, M. L. Smith, Marquard Smith +2
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Advanced Manufacturing and Logistics Optimization #Optimization and Search Problems

paper · doi:10.1287/opre.30.2.391

Abstract

We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness or the lateness of each job in the selected sequence. We present a polynomial bound scheduling algorithm for the solution of this problem along with the proof of optimality, a numerical example and discuss some extensions.

Related

• Common Due-Date Problem: Exact Polynomial Algorithms for a Given Job Sequence
• A Novel Approach to the Common Due-Date Problem on Single and Parallel Machines
• New Algorithms for Minimizing the Weighted Number of Tardy Jobs On a Single Machine
• An overview of some single machine scheduling problems: polynomial algorithms, complexity and approximability
• Single and Parallel Machine Scheduling with Variable Release Dates