Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine
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/Tmax. 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 Tmax constraint. Penalties arise if a job is completed outside the due window. 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.
Year of publication: |
2011
|
---|---|
Authors: | Su, Ling-Huey ; Tien, Yi-Yu |
Published in: |
International Journal of Production Economics. - Elsevier, ISSN 0925-5273. - Vol. 134.2011, 1, p. 196-203
|
Publisher: |
Elsevier |
Keywords: | Scheduling Single machine Common due window Mean absolute deviation Maximum tardiness |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Su, Ling-huey, (2011)
-
Su, Ling-Huey, (2011)
-
Scheduling on identical machines with batch arrivals
Chung, Tsui-Ping, (2010)
- More ...