A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling problems

摘要

Open shop scheduling problems (OSSP) are one of the most time-consuming works in scheduling problems. Currently, many artificial intelligence algorithms can reduce the problem-solving time to an acceptable time range, and even can further downsize the range of solution space. Although the range of solution space is technically downsized, in most scheduling algorithms every partial solution still needs to be completely solved before this solution can be evaluated. For example, if there is a schedule with 100 operations, then all 100 operations must be scheduled before the scheduler can evaluate its fitness. Therefore, the time–cost of unnecessary partial solutions is no longer saved.In order to improve the weakness stated above, this paper proposes a new bee colony optimization algorithm, with an idle-time-based filtering scheme, according to the inference of “the smaller the idle-time, the smaller the partial solution”, and the “smaller the makespan (Cmax) will be”. It can automatically stop searching a partial solution with insufficient profitability, while the scheduler is creating a new scheduling solution, and therefore, save time–cost for the remaining partial solution. The architecture and details of the bee colony optimization heuristic rule is detailed in this paper.