(582e) Real-Time Dynamic Hoist Scheduling under Uncertainties

Chemical processing and many manufacturing activities involve the handling of materials in multi-stage operational settings. Coating processes, such as electroplating and polymeric coating processes, are typical examples, where materials are usually handled by hoist(s). Each hoist is automatically controlled to carry jobs among processing units in a production line, according to a pre-set hoist schedule. Hoist schedule development, or hoist scheduling, is an integral part of design and operation for a manufacturing process. An optimal hoist schedule can improve significantly production efficiency and manufacturing cost. It is known that as high as 20% reduction in mean job waiting time and 50% improvement in standard deviation of cycle time can be reached in operations.

In a class of multi-product production lines, hoist scheduling has to confront a variety of uncertainties, such as random arrival of types of jobs, processing requirement change, processing unit availability, and job initial condition difference. These have made real-time dynamic hoist scheduling (RDHS) extremely difficult. Hitherto, available RDHS methods are mostly experience based and thus the solution optimality is not considered. Moreover, they are restricted to the problems where each unit could only have a single processing capacity. The other class of methods is mathematical programming based, where an optimization model is formulated and an optimal solution is sought by means of solution algorithms. A major problem by this class of methods is computational inefficiency, even for a small-scale scheduling problem. Hence, they are impractical for real-time application.

In this paper, a novel RDHS algorithm is introduced, which takes uncertainties into account and targets real-time applicability. The scheduling activities are motivated in a reactive way that any occurrence of process uncertainties will help initiate a new static schedule. Thus, the RDHS problem is actually implemented as a series of static scheduling problems, and in each of such problems, the hoist movements are programmed to make jobs to be processed as fast as possible. In order to guarantee the efficiency of each static schedule, a heuristic-rule based decomposition method is used to predict job-processing status first, and then to identify hoist movement sequence with a best-first search technique.

The efficacy of the proposed methodology is demonstrated by a successfully tackling of a real RDHS problem, where 16 units (including a plating unit with eight-job processing capacities and many cleaning and rinsing units) are employed in a production line to continuously process three different types of jobs. The application results show that any new hoist schedule can be generated in less than two seconds on a Pentium III PC with satisfactory optimal production rate.