Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints |
| |
Authors: | Zhixin Liu |
| |
Affiliation: | Department of Management Studies, College of Business, University of Michigan - Dearborn, Dearborn, MI 48126, USA |
| |
Abstract: | This paper considers the problem of finding a nonpreemptive schedule for a single machine to minimize the maximum lateness with release dates and precedence constraints. A branch and bound algorithm is developed. The algorithm uses four different heuristics to find upper bounds at the initial branch node: early release date heuristic, modified Schrage's heuristic, heuristic BLOCK, and a variable neighborhood descent procedure. At each branch node, two branches evolve from a schedule found by heuristic BLOCK using a binary branching rule based on bottleneck and critical jobs, and a lower bound is obtained by optimally solving the relaxed problem with preemption. The algorithm solves 14,984 out of the 15,000 systematically generated instances with up to 1,000 jobs within 1 minute of CPU time. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|