Load Scheduling of Simple Temporal Networks Under Dynamic Resource Pricing
Authors: T. K. Satish Kumar, Zhi Wang, Anoop Kumar, Craig Rogers, Craig Knoblock
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a polynomial-time algorithm for solving the load scheduling problem when f(t) is piecewise constant. This has important applications in many real-world domains including the smart home and smart grid domains. We then study the dependency of the unit price of the resource on time as well as the total demand at that time. This leads to a further characterization of tractable, NP-hard, and conjectured tractable cases. We provide a polynomial-time algorithm that finds a solution of minimum cost for the load scheduling problem on STNs when the unit price of energy is a piecewise constant function of time. Our polynomial-time algorithm was based on the idea of reducing this problem to the problem of computing the maximum weighed independent set in a POSET, which in turn was solved using a maxflow procedure. We then used the polynomial-time algorithm in a quasi binary search procedure to trade off makespan minimization against cost minimization. The paper primarily focuses on algorithm design, proofs, lemmas, and complexity analysis (e.g., polynomial-time algorithms, max-flow reductions, NP-hard characterizations). The |
| Researcher Affiliation | Academia | T. K. Satish Kumar Information Sciences Institute University of Southern California tkskwork@gmail.com Zhi Wang Department of Computer Science University of Southern California zhiwang@usc.edu Anoop Kumar, Craig Milo Rogers, Craig A. Knoblock Information Sciences Institute University of Southern California {anoopk, rogers, knoblock}@isi.edu |
| Pseudocode | Yes | Algorithm 1: Shows a maxflow-based polynomial-time procedure for solving the load scheduling problem on STNs for the minimization of cost under a piecewise constant f(t). Algorithm 2: Shows a quasi binary search algorithm for trading off makespan minimization against cost minimization within a suboptimality factor. |
| Open Source Code | No | The paper does not provide any statements about releasing code or links to source code repositories for the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and proofs. It mentions a |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for computations or experiments. |
| Software Dependencies | No | The paper mentions algorithms like |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments, thus no experimental setup details, hyperparameters, or training configurations are provided. |