Admissible Search Methods for Minimum Penalty Sequencing of Jobs with Setup Times on One and Two Machines

摘要

Many efficient implementations of AI search algorithms have been realized in recent years. In an effort to widen the area of application of search methods to problems that arise in industry, this paper examines the role that search can play in solving certain types of hard optimization problems that involve the proper sequencing of jobs in one-macliine job-shops and two-machine flow-shops. The problems studied here have the following general form: The completion of a job at time f induces a penalty G(f), where G(.) is a given penalty function which can be different for different jobs; the jobs must be so sequenced that the total penalty summed over all jobs is minimized. The objective is to improve upon current methods and to show that problems earlier considered formidable can at least be attempted, if not resolved satisfactorily, using admissible search algorithms. The crucial aspect is the derivation of good admissible heuristics that can direct the search narrowly to a goal. The search graph is not necessarily a tree. Algorithm A~* has been run on randomly generated data using the derived heuristic estimates to solve a variety of penalty minimization problems; some indicative experimental results are provided.