開放式工廠排程問題(Open Shop Scheduling Problem; OSSP)
是排程問題中最為耗費時間的工作之一。時至今日，許多人工智慧
演算法已經可以將解題時間縮短到可接受的時間範圍，甚至可以進
一步縮小解空間範圍。例如，由 Goncalves 等人提出了一個「參
數化主動式排程產生演算法」可以透過控制延遲時間來縮小解空間
範圍。D. Y. Sha 等人修改了計算延遲時間的函數而發表了mP-ASG
演算法以便更有效的控制解空間範圍。

雖然解空間範圍被技術性地縮小了，但是在大部份的排程演算
法裡每個部份解仍然必須完全被解完才可以被評估好壞。例如，有
一個排程包含了一百項動作，那麼在排程器評估此排程的適合度之
前，所有的一百項動作必須全部被排好。因此不必要的部份解所須
耗費的時間就無法被節省下來。

為了改進上述缺點，本文根據「閒置時間愈小的部份解，愈可
能得到較小的總完工時間」的推論，提出了一個具備以閒置時間為
基礎的過濾機制之新型蜜蜂群演算法，可以在排程器求取新解的過
程中自動停止搜尋收益率不足的解並因此節省了大量的求取剩餘的
部份解所耗費的時間。

Open Shop Scheduling Problem (OSSP) is one of
the most time-consuming works in scheduling problems.
Current days, 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. For example, Goncalves proposed
a Parameterized Active Schedule Generation (P-ASG)
algorithm. This algorithm can downsize the solution
space by controlling the delay-time. D. Y. Sha et al.
modified the delay-time function and proposed a
Modified Parameterized Active Schedule Generation
(mP-ASG) algorithm to control the range of solution
space more effectively.

Although the range of solution space is technically
downsized but in most of the scheduling algorithms
every partial solution still need to be solved
completely 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 for unnecessary partial solution can not be
saved anymore.

In order to improve the weakness described above,
this paper proposed A New Bee Colony Optimization
Algorithm with an Idle-Time-Based Filtering Scheme
according to the inference of“the smaller idle-time
a partial solution is, the smaller makespan (Cmax)
will be". It can automatically stop searching the
partial solution with unsuffient profitability while
the scheduler is making up a new scheduling solution
and therefore save a lot of time-cost for rest partial solution.

[1] Teodorovic, Dusan; Lucic, Panta; Markovic, Goran; Orco, Mauro Dell'.
Bee Colony Optimization: Principles and Applications.
NEUREL 2006.8th Seminar on 25-27 Sept.2006;151-156.

[2] D. Y. Sha, Cheng-Yu Hsu.
A new particle swarm optimization for the open shop scheduling problem.
Computers & Operations Research. 2008;35:3243-3261.

[3] D. Y. Sha, Cheng-Yu Hsu.
A modified parameterized active schedule generation algorithm for the job shop scheduling problem. The 36th CIE Conference on Computers & Industrial Engineering.2006;

[4] Garey MR, Johnson DS.
Computers and Intractability: a guide to the theory of NP-completeness.
Freeman, San Francisco.1979;

[5] Gonzalez T, Sahni S.
Open shop scheduling to minimize finish time.
Journal of the Association for Computing Machinery.1976;23(4):665-679.

[6] Brucker P, Hurink J, Jurisch B,Wostmann B.
A branch & bound algorithm for the open-shop problem.
Discrete Applied Mathematics.1997;76:43–59.

[7] Christelle Gueret, Christian Prins.
Classical and new heuristics for the open-shop problem: A computational evaluation.European Journal of Operational Research.1998;107:306-314.

[8] Ching-Fang Liaw.
A tabu search algorithm for the open shop scheduling problem.
Computers & Operations Research.1999;26:109-126.

[9] Giffler B, Thompson GL.
Algorithms for solving production scheduling problems.
Operations Research.1960;8(4):487–503.

[10] Christian Blum.
Beam-ACO - hybridizing ant colony optimization with beam search: an application to open shop scheduling.
Computers & Operations Research.2005;32:1565-1591.

[11] Frisch, Karl von.
The Dance Language and Orientation of Bees.
The Belknap Press of Harvard University Press.1967;

[12] Wenner, Adrian M., and Patrick H. Wells.
Anatomy of a Controversy: The Question of a "Language" Among Bees.
Columbia University Press.1990;

[13] David R. Tarpy.
THE DANCE LANGUAGE OF THE HONEY BEE.
Dissertation, NC state university.2009;
http://www.cals.ncsu.edu/entomology/apiculture/Dance_language.html
http://en.wikipedia.org/wiki/Honey_bee

[14] S. Camazine, J. Sneyd,
A Model of Collective Nectar Source by Honey Bees: Self-organization Through Simple Rules.Journal of Theoretical Biology.1991;149:547-571.

[15] Sushil J. Louis, Zhijie Xu.
Genetic algorithms for open shop scheduling and re-scheduling.
Dissertation. Department of Computer Science. University of Nevada.1996;

[16] Christian Prins.
Competitive genetic algorithms for the open-shop scheduling problem.
Dissertation. University of Technology of Troyes, Department of GSI.2000;

[17] Ching-Fang Liaw.
A hybrid genetic algorithm for the open shop scheduling problem.
European Journal of Operational Research.2000;124:28-42.

[18] Chin Soon Chong, Appa Iyer Sivakumar, Malcolm Yoke Hean Low, Kheng Leng Gay.
A bee colony optimization algorithm to job shop scheduling.
Proceedings of the 38th conference on Winter simulation, Winter Simulation Conference, IEEE.2006;

[19] Li-Pei Wong, Chi Yung Puan, Malcolm Yoke Hean Low, Chin Soon Chong.
Bee Colony Optimization algorithm with Big Valley landscape exploitation for Job Shop Scheduling problems.
Simulation Conference, 2008. WSC 2008. Winter 7-10 Dec,IEEE.2008;2050 - 2058.

[20] Wiest, J.D.
Some properties of schedules for large projects with limited resources.
Operations Research.1964;12:395-418.

[21] Arno Sprecher, Rainer Kolisch, Andreas Drexl.
Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem.
European Journal of Operational Research.1995;80:94-102.

[22] Gonçalves JF, Mendes JJ, de M, ResendeMGC.
A hybrid genetic algorithm for the job shop scheduling problem.
European Journal of Operational Research.2005;167(1):77–95.

[23] Taillard E.
Benchmarks for basic scheduling problems.
European Journal of Operations Research.1993;64:278–85.
http://ina2.eivd.ch/collaborateurs/etd/problemes.dir/ordonnancement.dir/ordonnancement.html

[24] Michael L. Pinedo
Scheduling Theory, Algorithms, and Systems.Springer.2008.

[25] Dervis Karaboga, Bahriye Basturk.
A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm.J Glob Optim.2007;39:459-471.

[26] Marco Dorigo, Vittorio Maniezzo, Albert Colorni.
Ant System: Optimization by a Colony of Cooperating Agents.
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS-PART B CYBERNETICS.1996;26:NO 1.

[27] James Kennedy and Russell Eberhart
Particle Swarm Optimization.IEEE.1995.

[28] John Henry Holland.
Adaptation in Natural and Artificial Systems:
An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence.,
Ann Arbor, MI: The University of Michigan Press, 1975

[29] Brian Huang.
Genetic Algorithm.
Dissertation. MMN Lab., Department of E.S., NCKU.2008.

[30] Marco Dorigo.
Ant Algorithms Solve Difficult Optimization Problems.
Lecture Notes In Computer Science;
Proceedings of the 6th European Conference on Advances in Artificial Life.
2001;2159:11-22.

[31] Y. M. Huang.
Particle Swarm Optimization.
Dissertation. MMN Lab., Department of E.S., NCKU.2008.

[32] Marco Dorigo, Luca Maria Gambardella.
Ant colonies for the travelling salesman problem.
BioSystems.1997;43:73–81.
[33] Giffler J, Thompson GL.
Algorithms for solving production scheduling problems.
Operations Research.1960;8:487–503.

[34] Brucker P, Hurink J, Jurisch B, Wostmann B.
New benchmark instances for the open shop problem.
ftp://ftp.mathematik.uni-osnabrueck.de/pub/osm/preprints/software/openshop/

[35] Christelle Gueret, Christian Prins.
Hard instances for the open shop problem.
http://www.emn.fr/x-auto/gueret/OpenShop/hard-os.zip

[36] Reeves, C. R.
Landscapes, operators and heuristic search.
Annals of Operations Research 86(0):473-490. 1999.

[37] Jason Chao-Hsien Pan, Han-Chiang Huang
A hybrid genetic algorithm for no-wait job shop scheduling problems.
Expert Systems with Applications.2009.36:5800–5806.

[38] Changsheng Zhang, Jigui Sun
An alternate two phases particle swarm optimization algorithm for flow shop scheduling problem.
Expert Systems with Applications.2009.36:5162–5167.

[39] I-Hong Kuo, Shi-Jinn Horng, Tzong-Wann Kao, Tsung-Lieh Lin, Cheng-Ling Lee, Takao Terano, Yi Pan.
An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model.
Expert Systems with Applications.2009.36:7027–7032.