Header menu link for other important links
X
An exact algorithm to minimize mean squared deviation of job completion times about a common due date
Published in
2013
Volume: 231
   
Issue: 3
Pages: 547 - 556
Abstract
We consider a deterministic n-job, single machine scheduling problem with the objective of minimizing the Mean Squared Deviation (MSD) of job completion times about a common due date (d). The MSD measure is non-regular and its value can decrease when one or more completion times increases. MSD problem is connected with the Completion Time Variance (CTV) problem and has been proved to be NP-hard. This problem finds application in situations where uniformity of service is important. We present an exact algorithm of pseudo-polynomial complexity, using ideas from branch and bound and dynamic programming. We propose a dominance rule and also develop a lower bound on MSD. The dominance rule and lower bound are effectively combined and used in the development of the proposed algorithm. The search space is explored using the breadth first branching strategy. The asymptotic space complexity of the algorithm is O(nd). Irrespective of the version of the problem - tightly constrained, constrained or unconstrained - the proposed algorithm provides optimal solutions for problem instances up to 1000 jobs size under different due date settings. © 2013 Elsevier B.V. All rights reserved.
About the journal
JournalEuropean Journal of Operational Research
ISSN03772217
Open AccessNo
Concepts (13)
  •  related image
    ASYMPTOTIC SPACE
  •  related image
    COMPLETION TIME VARIANCE
  •  related image
    DUE-DATE SETTING
  •  related image
    EXACT ALGORITHMS
  •  related image
    MEAN SQUARED DEVIATION
  •  related image
    Optimal solutions
  •  related image
    Problem instances
  •  related image
    SINGLE MACHINE SCHEDULING PROBLEMS
  •  related image
    Branch and bound method
  •  related image
    Dynamic programming
  •  related image
    Linear programming
  •  related image
    Scheduling
  •  related image
    Algorithms