Single machine MAD/Tmax problem with a common due date

Single machine MAD/Tmax problem with a common due date

0.00 Avg rating0 Votes
Article ID: iaor2003192
Country: United Kingdom
Volume: 29
Issue: 8
Start Page Number: 1099
End Page Number: 1113
Publication Date: Jul 2002
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

Consider a nonpreemptive single-machine scheduling problem which minimizes the MAD with a common due date d subject to the maximum tardiness constraint. This paper divides the MAD/Tmax problem into three categories: Δ-unconstrained, Δ-constrained, and tightly Δ-constrained cases. The exact algorithm to obtain the optimal solution is proposed after computing bounds to decide when the MAD/Tmax problem is Δ-unconstrained or tightly Δ-constrained cases. For the Δ-constrained MAD/Tmax problem, it is shown that the schedule should finish at (d + Δ) or a job should complete at d in the optimal schedule. In order to improve the efficiency of the proposed algorithm, three rules to delete partial sequences are developed. Since the MAD/Tmax problem is NP-complete in ordinary sense, a heuristic algorithm is proposed. In order to improve the schedule generated, the proposed algorithm uses the ideas that (1) in an optimal schedule, the largest job is not always processed first and (2) not all optimal schedules finish at d + Δ. For the obtained schedule and reverse schedule, shift operations and exchange operations are applied in order to improve the quality of solution. Computational results of test problems taken from the literature are shown.

Reviews

Required fields are marked *. Your email address will not be published.