Premium
Openshop scheduling under linear resources constraints
Author(s) -
Adiri I.,
Hamberg O.
Publication year - 1998
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199802)45:1<51::aid-nav3>3.0.co;2-k
Subject(s) - schedule , time complexity , scheduling (production processes) , computer science , operations research , resource (disambiguation) , order (exchange) , constant (computer programming) , mathematical optimization , linear programming , mathematics , business , algorithm , computer network , operating system , finance , programming language
Consider n jobs ( J 1 , …, J n ), m working stations ( M 1 , …, M m ) and λ linear resources ( R 1 , …, R λ ). Job J i consists of m operations ( O i1 , …, O im ). Operation O ij requires P k ( i , j ) units of resource R k to be realized in an M j . The availability of resource R k and the ability of the working station M h to consume resource R k , vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP‐hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998