Adaptive Agents and Multi-Agents Systems · 2016 · 39 citations · 25 references
EngineeringIndustrial EngineeringOperations ManagementAuction TheoryMulti-robot SystemsSchedulingConstraint SatisfactionMulti-robot SchedulingPrecedence RelationshipsSequential AuctionsTask AllocationTask SchedulingAuction AlgorithmsMulti-robot Task SchedulingPrioritizationScheduling Under Precedence ConstraintsScheduling With Precedence ConstraintsSequential Auction BiddingTask Precedence ConstraintsTask Scheduling For Robots
We consider the multi-robot task scheduling problem with precedence constraints, and introduce a general algorithm to approximate a solution to this problem. Our algorithm utilizes an iterated auction scheme, in which a batch of tasks that are pairwise unconstrained is selected in each iteration and scheduled using a modified sequential single-item auction. This algorithm also gains flexibility by allowing the use of task prioritization to order the scheduling process. We demonstrate the effectiveness of this iterated auction scheme empirically using existing 100- and 1000-task data sets that we have modified to include precedence constraints.
25
Bounds on Multiprocessing Timing Anomalies
Ron Graham · SIAM Journal on Applied Mathematics · 1969 · 2.4K citations
Rina Dechter, Itay Meiri, Judea Pearl · Artificial Intelligence · 1991 · 1.8K citations
Critical-path planning and scheduling
James E. Kelley, Morgan R. Walker · 1959 · 552 citations · Full text