Job sequencing with one common and multiple secondary resources: an A*/beam search based anytime algorithm

DOI10.1016/J.ARTINT.2019.103173MaRDI QIDQ2289017zbMATH OpenOpenAlexFDO

Authors Matthias Horn, Günther R. Raidl, Christian Blum

Publication date 20 January 2020

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10261/197461

zbMATH Keywords

schedulingsequencingA* algorithmbeam searchparticle therapy patient scheduling

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• \(\mathrm{A}^\ast\) search for prize-collecting job sequencing with one common and multiple secondary resources
• Simultaneous job scheduling and resource allocation on parallel machines
• A multi-objective approach to resource allocation in single machine scheduling
• scientific article; zbMATH DE number 3882186
• Job-shop scheduling with resource-time models of operations

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan
• A survey of scheduling problems with no-wait in process
• A survey of variants and extensions of the resource-constrained project scheduling problem
• Anytime heuristic search
• Anytime pack search
• Generalized best-first search strategies and the optimality of A*
• Heuristic search viewed as path finding in a graph
• Job shop scheduling with beam search
• Optimization models for radiotherapy patient scheduling
• Particle therapy patient scheduling with limited starting time variations of daily treatments
• Potential-based bounded-cost search and anytime non-parametric A*
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Sequencing jobs that require common resources on a single machine: A solvable case of the TSP
• Solving RCPSP/max by lazy clause generation
• The Three-Machine No-Wait Flow Shop is NP-Complete

Cited in

(2)

• \(\mathrm{A}^*\)-based construction of decision diagrams for a prize-collecting scheduling problem
• \(\mathrm{A}^\ast\) search for prize-collecting job sequencing with one common and multiple secondary resources

Describes a project that uses

Uses Software

• irace

This page was built for publication: Job sequencing with one common and multiple secondary resources: an A*/beam search based anytime algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2289017)