The UvA-LINKER will give you a range of other options to find the full text of a publication (including a direct link to the full-text if it is located on another database on the internet).
De UvA-LINKER biedt mogelijkheden om een publicatie elders te vinden (inclusief een directe link naar de publicatie online als deze beschikbaar is in een database op het internet).
faculty: "FEB" and publication year: "2006"
| Authors||C.W. Duin, E. van der Sluis|
|Title||On the complexity of Adjacent Resource Scheduling|
|Journal||Journal of Scheduling|
|Faculty||Faculty of Economics and Business|
|Institute/dept.||FEB: Amsterdam School of Economics Research Institute (ASE-RI)|
|Abstract||We study the problem of scheduling resource(s) for jobs in an adjacent manner (ARS). The problem relates to fixedinterval|
scheduling on one hand, and to the problem of two-dimensional strip packing on the other. Further, there is a
close relation with multiprocessor scheduling. A distinguishing characteristic is the constraint of resource-adjacency.
As an application of ARS, we 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 smoothen 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 time-interval 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 NP-complete. The complexity of the other problem
is already strongly NP-complete for two time periods. The paper also determines a number of cases that are solvable in
KEY WORDS: combinatorial optimization, multiprocessor scheduling, strip packing, integer programming
Use this url to link to this page: http://dare.uva.nl/en/record/226396
Contact us about this recordNotify a colleague
Add to bookbag