EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3943. Deriving Upper and Lower Bounds with Stochastic Dynamic Programming for Request Acceptance and Scheduling Decisions under Uncertainty
Invited abstract in session WB-52: Parallel Optimization and Scalability, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: 8003 (building: 202)
Authors (first author is the speaker)
| 1. | Marvin Caspar
|
| Business Information Systems & Operations Researc, RPTU Kaiserslautern-Landau | |
| 2. | Konstantin Kloster
|
| Business Studies and Economics, Technische Universität Kaiserslautern | |
| 3. | Oliver Wendt
|
| Business Research & Economics, University of Kaiserslautern |
Abstract
Sophisticated decision-making becomes necessary when weighing the value of accepting and simultaneously scheduling or rejecting a random incoming request now versus the value of waiting for another request in the future. This work proposes the Dynamic Request Acceptance and Unsplittable Scheduling Problem (DRAUSP), which considers a single resource with a given capacity over multiple homogeneous time slots. During each decision period within a fixed time horizon, a single random request arrives that demands capacity for some consecutive time slots and yields positive revenue if accepted. The objective becomes to accept or reject the incoming requests and, if accepted, to schedule them into available time slots to optimize the revenue collected over the time horizon. We use a Stochastic Dynamic Programming (SDP) algorithm to optimize the DRAUSP, which we model as a Markov decision process. In addition, we present a dimension compression technique to compute upper and lower bounds using SDP. Our computational study shows that we can derive appropriate bounds for some DRAUSP instances in reasonable computational time. Moreover, we conclude that basic heuristics, such as First Come First Serve, are insufficient to handle the complexity of DRAUSP and that more sophisticated heuristics are necessary to obtain adequate results.
Keywords
- Combinatorial Optimization
- Optimization Modeling
- Programming, Stochastic
Status: accepted
Back to the list of papers