Job-shop scheduling using certain heuristic search algorithms

This paper presents a family of sub-optimal algorithms based on the A* heuristic search algorithm, aimed at solving the general job-shop scheduling problem. A methodology is suggested for algorithms that require adjustable memory resources, by compromising algorithmic admissibility. Different possibilities for (admissible or non-admissible) heuristic estimates are suggested and dynamically weighted heuristics are introduced to the job-shop scheduling problem, with good results. Bottleneck scheduling is introduced within this problem-solving scheme, proving a base for more powerful heuristics. In terms of solution nearness to optimal and speed, the techniques investigated generally compare favourably with similar work in this field.