Evolutionary fragmentary algorithm for permutation flow shop problem
Рассматривается NP - трудная в сильном смысле задача Джонсона. Установлена фрагментарная структура задачи. Предложен эволюционно-фрагментарный подход для поиска оптимального решения. Ппроведено тестирование эволюционно-фрагментарного алгоритма на наборе тестовых задач из библиотеки ORLib. Ключевые с...
Saved in:
| Published in: | Таврический вестник информатики и математики |
|---|---|
| Date: | 2009 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Кримський науковий центр НАН України і МОН України
2009
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/18229 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Evolutionary fragmentary algorithm for permutation flow shop problem / O.S. Bondarenko, I.V. Kozin // Таврический вестник информатики и математики. — 2009. — № 2. — С. 47-51. — Бібліогр.: 18 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859660254504026112 |
|---|---|
| author | Bondarenko, O.S., Kozin, I.V. |
| author_facet | Bondarenko, O.S., Kozin, I.V. |
| citation_txt | Evolutionary fragmentary algorithm for permutation flow shop problem / O.S. Bondarenko, I.V. Kozin // Таврический вестник информатики и математики. — 2009. — № 2. — С. 47-51. — Бібліогр.: 18 назв. — англ. |
| collection | DSpace DC |
| container_title | Таврический вестник информатики и математики |
| description | Рассматривается NP - трудная в сильном смысле задача Джонсона. Установлена фрагментарная структура задачи. Предложен эволюционно-фрагментарный подход для поиска оптимального решения. Ппроведено тестирование эволюционно-фрагментарного алгоритма на наборе тестовых задач из библиотеки ORLib. Ключевые слова: задача Джонсона, фрагментарная структура, еволюционно-фрагментарный подход, NP - трудность.
Розглядається NP - важка в сильному сенсі задача Джонсона. Встановлено фрагментарну структуру задачі. Запропоновано еволюційно-фрагментарний підхід для пошуку оптимального розв'язку. Проведено тестування еволюційно-фрагментарного алгоритму на наборі тестових задач з бібліотеки ORLib. Ключові слова: задача Джонсона, фрагментарна структура, еволюційно-фрагментарний підхід, NP - важкість.
The article tackles the strongly NP - hard permutation flow shop problem. The flagmentary structure of the problem is pointed out. The evolutionary fragmentary approach for optimal solution is proposed. The testing of evolutionary fragmentary algorithm on instances' set from the ORLib library is conducted.
|
| first_indexed | 2025-11-30T09:41:29Z |
| format | Article |
| fulltext |
UDC 519.8EVOLUTIONARY FRAGMENTARY ALGORITHM FORPERMUTATION FLOW SHOP PROBLEM
Bondarenko O.S., Kozin I.V.Zaporizhzhya National UniversityThe Department of E
onomi
sThe Chair of E
onomi
Cyberneti
sZhukovsky str., 66, Zaporizhzhya, 69600, Ukrainee-mail: buenasdiaz�gmail.
omAbstra
t. The arti
le ta
kles the strongly N P-hard permutation �ow shop problem. Thefragmentary stru
ture of the problem is pointed out. The evolutionary fragmentary approa
h foroptimal solution is proposed. The testing of evolutionary fragmentary algorithm on instan
es' set fromthe ORLib [1℄ library is
ondu
ted. Introdu
tionIn 1954 Selmer Martin Johnson proposed an algorithm for �nding optimal solution toa problem [2℄, whi
h has been known sin
e as �ow shop problem.Suppose that n jobs Ji(i = 1; : : : ; n) are to be exe
uted on mma
hines Mj(j = 1; : : : ; m). Ea
h job
onsists of m operations Oi1; : : : ; Oim. Ea
hoperation Oij is asso
iated with the pro
essing time pij. Every job is pro
essed on allma
hines in the order of the ma
hine indexing. It means that the exe
ution of theoperation Oij+1 is not allowed until the exe
ution of the operation Oij is �nished. By thes
hedule we mean the mapping from the set of the job numbers (i; j) to the
ompletiontimes set Cij. In the given problem, we are supposed to �nd su
h a s
hedule in whi
h
omletion time of the last job on the last ma
hine is minimized. Preemption, pro
essingmore than one job on one ma
hine at a time, and exe
ution one job on more than onema
hine at a time are not allowed.A
ording to the notation [3℄ the problem under
onsideration is denoted F jjCmax.The problem has (n!)m feasible solutions, hen
e, in the literature the easier
ase is studied,whi
h admits n! s
hedules with the same order of pro
essing on all ma
hines (permutations
hedules) and is denoted F jprmujCmax. The latter
ase is
onsidered in the following.The exa
t algorithm proposed by Johnson solves the problem to optimality for m = 2
ase and for spe
ial
ase with m = 3. All the e�orts to �nd exa
t polynomial algorithmform > 2 were unsu
essfull. With the advent of the �rst results in the early 70-s [4, 5, 6℄ in
omputational
omplexity theory that fa
t had obtained an explanation. N P-hardnessin the strong sense was proved in [7℄. Sin
e then resear
hers' e�orts have been fo
used onapproximation and heuristi
algorithms design.Some time after that it has be
ome
lear that some problems are hard not only forsolving to optimality but are hard for approximating. It was proved [8℄ for
onsideredproblem there is no (1 + �)-approximation algorithm for 1 + � < 5=4. Furthermore, so farthe problem whether there exist polynomial approximation s
heme for FmjjCmax wherem
48 Bondarenko O.S., Kozin I.V.is �xed is open. Hen
e, the design of algorithms with no theoreti
al bounds and worst-
ase ratios, whi
h solve
omplex pra
ti
al problems, is now urgent. As su
h we
onsidersto
hasti
lo
al sear
h [9℄ algorithms: evolutionary algorithms, taboo sear
h, simulatedannealing, ant
olony systems, variable neighbourhood sear
h.The survey of lo
al sear
h algorithms for �ow shop problem
an be found in [10℄. The
omparative analysis of the most e�
ient lo
al sear
h methods from the literature,
alledalso metaheuristi
s, was
ondu
ted in [11℄.The goal of the paper is the inquiry of the new solution approa
h to
ombinatorialproblems based on the
ombination of the evolutionary and the fragmentary approa
hes.1. The Fragmentary Stru
tureDe�nition 1. Fragmentary stru
ture [12℄ is tuple (X ;Y ;R), where X � a �nite set ofthe fragments, Y � a family of subsets of X , R � a
ombining rule, i.e. the de
ision rulefor re
ognizing whether a union of subsets of X is a feasible set of Y .F jjCmax
an be
onsidered as the fragmentary stru
ture. By fragmments we will haveany tuples of jobs, respe
tively by the elementary fragments we will mean jobs. The ruleof
ombination � no job repetition in the
ombined tuples. Maximal by in
lusion fragmentwill be a feasible solution the problem under
onsideration. So the feasible solution
anbe
onsidered as
ertain �xed permutation of jobs.In the papers [12, 13℄ it has been showed that the sear
h of feasible solutions
an
onsidered in the fragmentary stru
ture framework. For the
ostru
tion of feasiblesolutions the fragmentary algorithm F is applied. In the general
ase, the input of Falgorithm are a tuple I = (i1; : : : ; in) and the empty solution set S . The input is lookedthrough by F in the ma
hine indexing order. On every step in the tuple I the �rstelement is looked for whi
h the
ombining rule is ful�lled. The found elementary fragmentis added into S . The pro
edure is repeated until the maximal by in
lusion fragment isbuilt. 2. The Evolutionary Fragmentary AlgorithmThe fragmentary algorithm allows to obtain only some feasible solutions for theoptimization problem. For �nding optimal solution of F jprmujCmax the
ombinationevolutionary and fragmentary approa
hes is proposed. A few analogous approa
hesgrounded on the evolutionary me
hanism and performan
e evaluation of su
h approa
hesare
onsidered in [14, 15℄.The des
ription of evolutionary fragmentary algorithm (EVF algorithm), exploredin the work, is the following. The feasible solutions of the problem are presented by jobnumber permutations, whi
h form the set of all permutations I1; : : : ; In!. Ea
h permutationwill be treated as
hromosome. The sear
h
an be des
ribed as the following.Stage 1. Initialization.The initial population,
onsisting of N
hromosomes, is generated at random.Stage 2. Sele
tion.Sele
t K pairs of parents from the
urrent population for reprodu
tion. The sele
tionis random without repla
ement. ¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �2' 2009
EVF algorithm for permutation �ow shop problem 49Stage 3. Re
ombination.The re
ombination in the EVF algorithm is implemented by the following n-steppro
edure. All the pairs of
hromosome-parents' I-tuples are being looked through. Onevery step the minimal element from the �rst two elements of I-tuples' pair is
hosen andis inserted into tuple-o�spring. The inserted element is deleted from both tuples-parents.For instan
e, in the
ase with m = 5
hromosome-parents [12543℄ and [53142℄ yield the
hromosome-o�spring [12534℄.Stage 4. Mutaion.The mutation is implemented by transposition of jobs' indexes from two randomlysele
ted positions in
hromosome.Stage 5. Repla
ement.The
hromosomes-o�springs are added in the
urrent population. The shrinking of the
urrent population to prede�ened size is provided by sequential deletion of
hromosomeswith maximal
riterion's values, where the
riterion's value is
omputed by the followingre
ursive formula: Ci;j = maxfCi�1;j; Ci;j�1g+ pi;jStage 6. Termination.If prede�ened termination
riterion is a
hieved, then stop the algorithm, otherwisego to the se
ond stage. The termination
riterion, used by authors, is the number ofgenerations in evolution, i.e. the number of the sear
h stages repetitions.3. The Test ResultsThe ne
essity of test
ondu
tion is explained by the di�
ulties and, sometimes, byimposibility of theoreti
al estimation of sto
hasti
lo
al sear
h algorithms performan
ederivaton in general, and of evolutionary algorithms, in parti
ular.For the EVF algorithm performan
e veri�
ation the test was being
ondu
ted onwell-known in the Taillard's [16℄ problem set. The problem set
omprises twelve groups
onsisting of ten instan
es ea
h with the numbers of jobs from 20 to 500 and the numberof ma
hines from �ve to 20. It is the most used in the literature for F jprmujCmax testing.Thus, there appears an opportunity for the
omparison of the proposed algorithm withalready existing and tested ones on the given set.EVF algorithm was tested against random sear
h (RS) algorithm as well as NEHalgorithm [17℄, whi
h is
urently
onsidered the best performing deterministi
heuristi
.All the three algorithms were implemented in Visual Basi
for Appli
ations andrun on
omputer with Celeron pro
esor 1800 Mhz and 256 MB of the main memory.The termination
riterion was
hosen to be the number of generations. a
hieved by thealgorithm during its run.The algorithms' performan
e was measured by relative devian
e (RD) from optimum(OPT) or the least known upper bound [18℄ of the value (A) found by given algorithm:RD = A�OPTOPT � 100:In Table 1 ea
h group of problems is denoted as n�m, where n is the number of jobs,m is the number of ma
hines. In it RD for ea
h instan
e is averaged on the group size. ForEVF algorithm in the table in the parentheses the number of generations during whi
h it¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �2' 2009
50 Bondarenko O.S., Kozin I.V.Group of problems RS NEH EVF20� 5 6.95 2.46 1.25 (300)20� 10 10.29 4.88 2.86 (300)20� 20 8.52 3.72 3.28 (300)50� 5 5.18 0.81 0.92 (300)50� 10 14.39 5.23 4.51 (300)50� 20 16.71 6.21 5.85 (300)100� 5 4.14 0.67 0.73 (500)100� 10 10.74 2.45 2.4 (500)100� 20 16.85 5.72 6.08 (500)200� 10 8.74 1.8 1.52 (1000)200� 20 15.66 4.66 4.95 (1000)500� 20 11.79 2.41 3.74 (1000)Average 10.83 3.42 3.17Òàáëèöà 1. The Test Results for F jprmujCmaxwas run is pointed out. From Table 1 it
an be
on
luded that in the average evolutionaryfragmentary algorithm has showed the higher results than other two tested algorithms.Con
lusionThe basi
result of the paper is the new approa
h to s
heduling problems solution. Thefragmentary stru
ture has been showed whi
h allows the appli
ation of EVF algorithm.The testing of the algorithm on the standard problem set is ful�lled.From the test results, represented in Table 1, it appears promising to apply theproposed aproa
h to s
heduling problems solution.Ñïèñîê ëèòåðàòóðû1. Beasley J. E. ORLib - Operations Resear
h Library.http://people.brunel.a
.uk/�mastjjb/jeb/orlib/�les/�owshop2.txt, 2008.2. Johnson S. M. Optimal Two and Three-Stage Produ
tion S
hedules with Setup Times In
luded //Naval Resear
h Logisti
s Quarterly. � 1954. � Vol. 1, No. 1. � P. 61�68.3. Graham R. L. Optimization and approximation in deterministi
sequen
ing and s
heduling:A survey / R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan // Dis
reteOptimization II / P.L. Hammer, E.L. Johnson and B.H. Korte (eds.). � Amsterdam : North-Holland,1979. � (Annals of Dis
rete Mathemati
s ; Vol. 5.). � P. 287�326.4. Cook S. A. The
omplexity of theorem-proving pro
edures / Stephen A. Cook // STOC '71:Pro
eedings of the third annual ACM symposium on Theory of
omputing. � New York : ACM,1971. � P. 151�158.5. Karp R. Redu
ibility among Combinatorial Problems // Complexity of Computer Computations /R. E. Miller and J. W. That
her (eds.). � New York : Plenum Press, 1972. � P. 85�104.6. Ëåâèí Ë. À. Óíèâåðñàëüíûå çàäà÷è ïåðåáîðà / Ë. À. Ëåâèí // Ïðîáëåìû ïåðåäà÷è èí�îðìà-öèè. � 1973. � Ò. 9, � 3. � Ñ. 115-116. ¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �2' 2009
EVF algorithm for permutation �ow shop problem 517. Garey M. R. The Complexity of Flow Shop and Job Shop S
heduling / M. R. Garey, D. S. Johnson,R. Sethi // Mathemati
s of Operations Resear
h. � 1976. � Vol. 1, No. 2. � P. 117�129.8. Williamson D. P. Short shop s
hedules / D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J.Hurkens, J. K. Lenstra, S. V. Sevastianov, D. B. Shmoys // Operations Resear
h. � 1997. � Vol. 45,No. 2. � P. 288�294.9. Hoos H. H. Sto
hasti
Lo
al Sear
h : Foundations and Appli
ations / Hoos H. H., Stuetzle T. � SanFran
is
o : Morgan Kaufmann Publishers, 2004. � 660 p. � ISBN 1-55860-872-9.10. Ruiz R. A
omprehensive review and evaluation of permutation �owshop heuristi
s / R. Ruiz, C.Maroto // European Journal of Operational Resear
h. � 2005. � Vol. 165. � P. 479�494.11. Ruiz R. A simple and e�e
tive iterated greedy algorithm for the permutation �owshop s
hedulingproblem / R. Ruiz, T. Stuetzle// European Journal of Operational Resear
h. � 2007. � Vol. 177. �P. 2033�2049.12. Êîçèí È. Â. Ôðàãìåíòàðíûå àëãîðèòìû â ñèñòåìàõ ïîääåðæêè ïðèíÿòèÿ ðåøåíèé // Ïèòàííÿïðèêëàäíî¨ ìàòåìàòèêè i ìàòåìàòè÷íîãî ìîäåëþâàííÿ, çáiðíèê íàóêîâèõ ïðàöü. - Äíiïðîïåòðî-â
üê. � 2006. � Ñ. 131�137.13. Êîçèí È. Â. Ôðàãìåíòàðíûé àëãîðèòì äëÿ çàäà÷è ñèììåòðè÷íîãî ðàçìåùåíèÿ // �àäèîýëåê-òðîíèêà, èí�îðìàòèêà, óïðàâëåíèå. � 2005. � � 1. � Ñ. 76�83.14. Ruiz R. Two new robust geneti
algorithms for the �owshop s
heduling problem / R. Ruiz, C. Maroto,J. Al
araz // OMEGA, the International Journal of Management S
ien
e. � 2006. � Vol. 34. � P.461�476.15. Nagano M. S. A Constru
tive Geneti
Algorithm for permutation �owshop s
heduling / M. S. Nagano,R. Ruiz, L. A. N. Lorena // Computers & Industrial Engineering. � 2008. � Vol. 55. � P. 195�207.16. Taillard E. Ben
hmarks for basi
s
heduling problems // European Journal of Operational Resear
h. �1993. � Vol. 64, No. 2. � P. 278-285.17. Nawaz M. A heuristi
algorithm for the m-ma
hine, n-job �ow-shop sequen
ing problem / M. Nawaz,E. E. Ens
ore Jr., I. Ham // OMEGA, The International Journal of Management S
ien
e. � 1983. �Vol. 11, No. 1. � P. 91�95.18. Taillard E. Summary of best known lower and upper bounds of Taillard's instan
es.http://ina2.eivd.
h/Collaborateurs/etd/problemes.dir/ordonnan
ement.dir/�owshop.dir/best_lb_-up.txt, 2008. Ñòàòüÿ ïîñòóïèëà â ðåäàêöèþ 15.08.2009
¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �2' 2009
|
| id | nasplib_isofts_kiev_ua-123456789-18229 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1729-3901 |
| language | English |
| last_indexed | 2025-11-30T09:41:29Z |
| publishDate | 2009 |
| publisher | Кримський науковий центр НАН України і МОН України |
| record_format | dspace |
| spelling | Bondarenko, O.S., Kozin, I.V. 2011-03-18T23:43:13Z 2011-03-18T23:43:13Z 2009 Evolutionary fragmentary algorithm for permutation flow shop problem / O.S. Bondarenko, I.V. Kozin // Таврический вестник информатики и математики. — 2009. — № 2. — С. 47-51. — Бібліогр.: 18 назв. — англ. 1729-3901 https://nasplib.isofts.kiev.ua/handle/123456789/18229 519.8 Рассматривается NP - трудная в сильном смысле задача Джонсона. Установлена фрагментарная структура задачи. Предложен эволюционно-фрагментарный подход для поиска оптимального решения. Ппроведено тестирование эволюционно-фрагментарного алгоритма на наборе тестовых задач из библиотеки ORLib. Ключевые слова: задача Джонсона, фрагментарная структура, еволюционно-фрагментарный подход, NP - трудность. Розглядається NP - важка в сильному сенсі задача Джонсона. Встановлено фрагментарну структуру задачі. Запропоновано еволюційно-фрагментарний підхід для пошуку оптимального розв'язку. Проведено тестування еволюційно-фрагментарного алгоритму на наборі тестових задач з бібліотеки ORLib. Ключові слова: задача Джонсона, фрагментарна структура, еволюційно-фрагментарний підхід, NP - важкість. The article tackles the strongly NP - hard permutation flow shop problem. The flagmentary structure of the problem is pointed out. The evolutionary fragmentary approach for optimal solution is proposed. The testing of evolutionary fragmentary algorithm on instances' set from the ORLib library is conducted. en Кримський науковий центр НАН України і МОН України Таврический вестник информатики и математики Evolutionary fragmentary algorithm for permutation flow shop problem Article published earlier |
| spellingShingle | Evolutionary fragmentary algorithm for permutation flow shop problem Bondarenko, O.S., Kozin, I.V. |
| title | Evolutionary fragmentary algorithm for permutation flow shop problem |
| title_full | Evolutionary fragmentary algorithm for permutation flow shop problem |
| title_fullStr | Evolutionary fragmentary algorithm for permutation flow shop problem |
| title_full_unstemmed | Evolutionary fragmentary algorithm for permutation flow shop problem |
| title_short | Evolutionary fragmentary algorithm for permutation flow shop problem |
| title_sort | evolutionary fragmentary algorithm for permutation flow shop problem |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/18229 |
| work_keys_str_mv | AT bondarenkoos evolutionaryfragmentaryalgorithmforpermutationflowshopproblem AT koziniv evolutionaryfragmentaryalgorithmforpermutationflowshopproblem |