《1990 Scheduling jobs with simple precedence constraints on parallel machines》.pdf

Scheduling Jobs with Simple Precedence Constraints on Parallel Machines Debra J. Hoitomt, Peter B. Luh, Eric Max, and Krishna R. Pattipati ABSTRACT: This article presents a meth- action of jobs, as they compete for limited odology for scheduling jobs on identical, resources, is not visible; dynamic changes in parallel machines. Each job is comprised of the system (for example, machine break- a small number of operations that must be down, jobs requiring more time than antic- processed in a specified order. The objective ipated, etc.) cannot be easily accommo- is to minimize the total weighted quadratic dated; and job completion dates cannot be tardiness of the schedule, subject to capacity accurately predicted or controlled. Conse- and precedence constraints. The procedure quently,jobs often have long lead times, and presented here is an efficient near-optimal shops are loaded with excessive work-in- method based on the Lagrangian relaxation process inventories. Therefore, the resolu- technique and the list-scheduling concept. In tion of these difficulties can translate into addition, the resulting job-interaction infor- considerable direct and indirect cost savings. mation can be used to provide quick answers In this article, we consider the non- to “what-if” questions and to reconfigure preemptive scheduling ofjobs with due dates the schedule to incorporate new jobs and on id