Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine

作者：Su Ling Huey^*; Tien Yi Yu

来源：International Journal of Production Economics, 2011, 134(1): 196-203.

DOI：10.1016/j.ijpe.2011.06.016

• Scheduling
• Single machine
• Common due window
• Mean absolute deviation
• Maximum tardiness

This study deals with the problem of scheduling jobs on a single machine to minimize the mean absolute deviation of the job completion time about a large common due window subject to the maximum tardiness constraint. Using the well-known three-field notation, the problem is identified as MAD/large DueWindow/T(max). The common due window is set to be large enough to allow idle time prior to the beginning of a schedule to investigate the effect of the T(max) constraint. Penalties arise if a job is completed outside the due A branch and bound algorithm and a heuristic are proposed. Many properties of the solutions and precedence relationships are identified. Our computational results reveal that the branch and bound algorithm is capable of solving problems of up to 50 jobs and the heuristic algorithm yields approximate solutions that are very close to the exact solution.

• 出版日期2011-11