Feasibility of Hungarian Algorithm based Scheduling

An optimal resource allocation algorithm, Hungarian algorithm, is not directly applicable to manufacturing scheduling problems, because solutions of resource allocation problems may violate precedence constraints among processes that constitute individual manufacturing jobs. To apply Hungarian algorithm to scheduling problems, in this paper, several strategies for assigning prices to time slots of individual machines, which are allocated to processes, are proposed. Preliminary experimentation results showed that these strategies can generate near optimal schedules, i.e. when lengths of scheduling horizons were larger than 3 times of the maximum lengths of jobs, generated schedules could complete given jobs while maintaining the deterioration of the efficiency less than 5% from optimal schedules