Scheduling problems with due date objectives and constraints.

摘要

Due dates are often the primary objective of manufacturing managers, particularly in plants that manufacture components for large assembly plants. This dissertation addresses three scheduling problems that regard the due date concern as either an objective or a constraint. Also of interest is the grouping of jobs with common manufacturing characteristics into part families. The advantage of grouping being a sequence independent setup required only when changing between jobs of different part families.; The first problem is a single machine problem with the objective of minimizing the maximum lateness for jobs with sequence independent setups. A heuristic procedure is shown to provide optimal/near optimal solutions over a wide range of problems. It performs well compared to other heuristics, and is shown to be effective in finding solutions for large problems.; The second problem is a single machine deadline problem with the objective of minimizing setup and holding cost for jobs with sequence independent setups. A branch and bound procedure is shown to provide optimal solutions over a range of problems.; The last problem is the classic job shop scheduling problem with the objective of minimizing the maximum lateness. A simulated annealing procedure is shown to obtain new upper bounds on benchmark problems. The annealing procedure is also shown to perform well as an improvement procedure for large scale job shop problems.