Query:
faculty: "FEB" and publication year: "2004"
Authors  C.W. Duin, E. van der Sluis  Title  On the complexity of adjacent resource scheduling 
Publisher  Institute of Actuarial Science & Econometrics 
Place  Amsterdam 
Year  2004 
Pages  22 
Title series  Report AE 
Series number  6/2004 
Faculty  Faculty of Economics and Business 
Institute/dept.  FEB: Amsterdam School of Economics Research Institute (ASERI) 
Abstract  We study the problem of scheduling resource(s) for jobs in an adjacent manner (ARS). The problem relates to fixed interval scheduling on the one hand, and to the problem of twodimensional strip packing on the other hand. Further, there is a close relation with multiprocessor scheduling. A distinguishing characteristic is the constraint of resourceadjacency. As an application of ARS, consider an airport where passengers check in for their flight, joining lines before one or more desks; at the desk the luggage is checked and so forth. To smooth these operations the airport maintains a clear order in the waiting lines: a number n(f) of adjacent desks is to be assigned exclusively during a fixed timeinterval I(f) to flight f. For each flight in a given planning horizon of discrete time periods, one seeks a feasible assignment to adjacent desks and the objective is to minimize the total number of involved desks. The paper explores two problem variants and relates them to other scheduling problems. The basic, rectangular version of ARS is a special case of multiprocessor scheduling. The other problem is more general and it does not fit into any existing scheduling model. After presenting an integer linear program for ARS, we discuss the complexity of both problems, as well as of special cases. The decision version of the rectangular problem remains strongly NPcomplete. The complexity of the other problem is already strongly NPcomplete for two time periods. The paper also determines a number of cases that are solvable in polynomial time. 
Document type  Report 
Download  
Document finder 

Use this url to link to this page: http://dare.uva.nl/en/record/392743
Contact us about this recordNotify a colleague
Add to bookbag
