THE WEIGHTED COMMON DUE-DATE SINGLE-MACHINE SCHEDULING PROBLEM REVISITED

This paper deals with the earliness-tardiness common due date model of minimizing the sum of earliness and tardiness penalties. We assume th at those penalties vary from job to job and that the ratios of process ing times and penalties satisfy certain (called agreeable) conditions. Three types of schedules (V-0, V-1, and W) are identified where the c omplexity of W schedules far exceeds the complexity of the remaining t ypes. Conditions are derived that significantly improve the existing m ethods to find the best W schedule. This improvement is demonstrated o n 1500 test problems of the sizes n = 10, 20, 50, 70 and 100.