A vector space model for variance reduction in single machine scheduling

S. Cho, V. V. Prabhu

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


Reducing the variance of part completion times about promised due dates is an important element of Just-In-Time production because it reduces the work-in-process inventory and tardiness simultaneously. Scheduling models and algorithms are developed to minimize the Mean Squared Deviation (MSD) of completion times about due dates on a single machine. A generic model is developed in real vector space for understanding the structural relationship between the optimal schedule and the location of the due dates. Geometric insights gained from this vector space model are used to relate the shortest and longest processing time sequences to the level of difficulty of the MSD optimization problem. The vector space model is used to develop dominance conditions for a branch and bound algorithm and to analytically synthesize parameters for a continuous variable feedback control algorithm for distributed scheduling. The control algorithm lends itself to massively parallel distributed computation and is found to produce near optimal solutions efficiently, which makes it more scalable and practical compared to the branch and bound algorithm. Computational experiments with both approaches are presented.

Original languageEnglish (US)
Pages (from-to)933-952
Number of pages20
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number11
StatePublished - Nov 2002

All Science Journal Classification (ASJC) codes

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'A vector space model for variance reduction in single machine scheduling'. Together they form a unique fingerprint.

Cite this