We consider an environment where a production facility modeled as a single machine needs to assign delivery dates to several orders and find a feasible sequence. Tardy jobs are not allowed. The delivery dates are to be at prespecified fixed intervals. The objective is to minimize the due date penalty and the cost of earliness. We provide a dynamic programming‐based solution procedure that runs in polynomial time. We develop several dominance results that reduced the computational requirement by an order of magnitude in our computational study.
AhmadiR. and BagchiU. (1986), “Single Machine Scheduling to Minimize Earliness Subject to Deadlines,” Working Paper 86/86–4–17, Department of Management, University of Texas, Austin.
2.
BagchiU.SullivanR. S., and ChangY. L. (1986), “Minimizing Mean Absolute Deviation of Completion Times About a Common Due Date,”Naval Research Logistics Quarterly, 33, 2, 227–240.
3.
ChandS. and ChhajedD. (1992), “A Single‐Machine Model for Determination of Optimal Due Dates and Sequence,”Operations Research, 40, 3, 596–602.
4.
ChandS. and SchneebergerH. (1988), “Single Machine Scheduling to Minimize Weighted Earliness Subject to No Tardy Jobs,European Journal of Operational Research, 34, 3, 221–230.
5.
ChengT. C. E. and KahlbacherH. G. (1991), “Scheduling with Delivery and Earliness Penalties,” Working Paper, University of Manitoba.
6.
ChhajedD. (1994), “A Fixed Interval Due‐Date Scheduling Problem with Earliness and Due‐Date Costs,” forthcoming in European Journal of Operational Research..
7.
DeP.GhoshJ. B., and WellsC. E. (1991), “Optimal Delivery Time Quotation and Order Sequencing,”Decision Sciences, 22, 2, 379–390.
8.
GareyM. R.TarjanR. E., and WilfongG. T. (1988), “One‐Processor Scheduling with Earliness and Tardiness Penalties,”Mathematics of Operations Research, 13, 3, 330–348.
9.
HallN. G.KubiakW., and SethiS. P. (1991), “Earliness‐Tardiness Scheduling Problems. II. Deviation of Completion Times About a Restrictive Common Due Date,”Operations Research, 39, 5, 847–856.
10.
KanetJ. J. (1981), “Minimizing the Average Deviation of Job Completion Times About a Common Due Date,”Naval Research Logistics Quarterly, 28, 4, 643–651.
11.
LeeC.‐Y. and LiC.‐L. (1993), “On the Fixed Interval Due‐Date Scheduling Problem,” Research Report 93–25, Department of Industrial and Systems Engineering, University of Florida, Gainesville.
12.
MatsuoH. (1988), “The Weighted Total Tardiness Problem with Fixed Shipping Times and Overtime Utilization,”Operations Research, 36, 2, 293–307.
13.
PanwalkarS. S.SmithM. L., and SeidmannA. (1982), “Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem,”Operations Research, 30, 2, 391–399.
