An Equilibrium Principle on the AON Network for Single-Machine Scheduling Problem with Time Lags

The NP-hard single-machine scheduling problem with time lags while minimizing the completion time could be described with an AON (Activity-On-Node) network. An equilibrium principle was discovered and proved on the AON network for single-machine scheduling problem. As a testing problem, plate hot rolling scheduling is a type of single-machine scheduling problem with time lags. For the scheduling problem, a nonlinear mathematic optimization model, which maximizes utilization of the rolling mill, was established based on the equilibrium principle and was solved by software LINGO. Computation examples demonstrated that the new method could solve effectively the single-machine scheduling problem with time lags by equilibrium principle on the AON network.