(400f) Real-Time and Rigorous Dynamic Hoist Scheduling

Chuanyu Zhao, Jie Fu and Qiang Xu*

Dan F. Smith Department of Chemical Engineering

Lamar University, Beaumont, TX 77710, USA

Abstract

Dynamic hoist scheduling is often employed on-line for multi-stage material handling under consideration of simultaneously processing multiple types of jobs with different processing recipes.  Unlike other scheduling problems, dynamic hoist scheduling requires multiple job processing time and changeover time to be precisely controlled by hoist movements.  The objective is to maximize the job throughput of a production line.  Dynamic hoist scheduling can be very complicated when various production uncertainties are considered, such as the random arrival of random types of jobs with different processing recipes.  Furthermore, if stringent constraints such as multi-job processing capacity at some process stages and the real-time schedule implementation requirements are also taken into account, the mathematical-programming based solution identification for such a scheduling problem will be very challenging.

Hitherto, available methods are mostly heuristic based, and thus the solution optimality or even feasibility can not be guaranteed.  In this paper, an MILP based modeling methodology is introduced to solve the real-time, multi-job capacity, and multi-recipe dynamic hoist scheduling, which has never been reported before.  The MILP model covers all the major dynamic hoist scheduling issues.  The online dynamic scheduling problem can be separated by a series of static scheduling problems.  Each static hoist scheduling problem is triggered and solved reactively by every addition of jobs.  For real-time application, the solving time for each static scheduling problem should be considered.  When a job arrives, with the estimation of solving time of the reschedule, the expecting job and hoist information are collected, which will be used as the initial conditions of the rescheduling.   

The efficacy of the proposed methodology is demonstrated by successfully tackling a real-time dynamic hoist scheduling problem, where 8 units with various capacities are employed in the production line to continuously produce three different types of jobs.  Many case studies with various coming jobs and random arrival time are modeled and solved in GAMS version 23.3 with the solver CPLEX.  The average solving time on an 8-Core Xeon 3.2GHz Dell server for the case studies is less than 0.6 seconds meanwhile, the scheduling results are also guaranteed as the global optimal. 

Keywords: Hoist Scheduling, MILP, Dynamic scheduling, Real-time Optimization,