A simple mixed integer programming model for the N job/single machine scheduling problem with possibly sequence‐dependent setup times, differing earliness/tardiness cost penalties, and variable due dates is proposed and evaluated for computational efficiency. Results indicated that the computational effort required to reach optimality rose with the number of jobs to be scheduled and with decreased variance in due dates. Though computational effort was significant for the largest problems solved, the model remained viable for optimizing research scale problems.
BagchiU.SullivanR. S., and ChangY. L. (1986), “Minimizing Mean Absolute Deviation of Completion Times About a Common Due Date,”Naval Research Logistics Quarterly, 33, 227–240.
2.
BagchiU.SullivanR. S., and ChangY. L. (1987), “Minimizing Mean Squared Deviation of Completion Times About a Common Due Date,”Management Science, 33, 894–906.
3.
BakerK. R. (1974), Introduction to Sequencing and Scheduling, John Wiley and Sons, Inc., New York.
4.
DavisJ. S. and KanetJ. J. (1987), “Single Machine Scheduling with a Non‐Regular Performance Measure,” Unpublished working paper, Clemson University.
5.
FryT. D.ArmstrongR. D., and BlackstoneJ. H. (1987), “Minimizing Weighted Absolute Deviation in Single Machine Scheduling,”IIE Transactions, 19, 445–450.
6.
HallN. G. (1986), “Single and Multiple‐Processor Models for Minimizing Completion Time Variance,”Naval Research Logistics Quarterly, 33, 49–54.
7.
KanetJ. J. (1981), “Minimizing the Average Deviation of Job Completion Times About a Common Due Date,”Naval Research Logistics Quarterly, 28, 643–651.
8.
LakshminarayanS.LakshmananR.PapineauR. L., and RochetteR. (1978), “Optimal Single‐Machine Scheduling with Earliness and Tardiness Penalties,”Operations Research, 26, 1079–1082.
9.
OwP. S. and MortonT. E. (1988), “Filtered Beam Search in Scheduling,”International Journal of Production Research, 26(1), 35–62.
10.
OwP. S. and MortonT. E. (1989), “The Single Machine Early/Tardy Problem,”Management Science, 35, 177–191.
11.
PanwalkerS. S.SmithM. L., and SeidmannA. (1982), “Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem,”Operations Research, 30, 391–399.
12.
SeidmannA.PanwalkerS. S., and SmithM. L. (1981), “Optimal Assignment of Due‐Dates for a Single Processor Scheduling Problem,”International Journal of Production Research, 19, 393–399.
13.
SidneyJ. B. (1977), “Optimal Single‐Machine Scheduling with Earliness and Tardiness Penalties,”Operations Research, 25, 62–69.
14.
SundararaghavanP. S. and AhmedM. U. (1984), “Minimizing the Sum of Absolute Lateness in Single‐Machine and Multi‐Machine Scheduling,”Naval Research Logistics Quarterly, 31, 325–333.
