Article

Article title SELECTIVE-PERMUTATION METHOD FOR FINDING AN APPROXIMATE SOLUTION OF THE OPEN SHOP SCHEDULING PROBLEM. COMBINATIONAL PERMUTATIONS
Authors R.A. Neidorf, A.A. Zhikulin
Section SECTION V. MODELLING OF COMPLEX SYSTEMS
Month, Year 07, 2013 @en
Index UDC 681.3.681.5
DOI
Abstract The effective method for improving selective-permutation algorithm precision to  solve the job-shop scheduling problems based on combinational multipermutations and equivalent permutations is proposed. Multipermutations are used for improving the solution by exchanging several jobs between executors simultaneously and equivalent permutations change the solution structure saving its estimate. This approach expands the algorithm searching space what leads to increasing the probability of an absolute optimum finding in several times under certain conditions. Experimental results are presented.

Download PDF

Keywords Job-shop problem; selective-permutation algorithm; single permutation; multipermutation; equipermutation.
References 1. Коффман Э.Г. Теория расписания и вычислительные машины. – М., 1984.
2. Нейдорф Р.А. Селективно-перестановочный метод решения задач параллельного распределения заданий между исполнителями. Одинарные перестановки // Вестн. Донск. гос. техн. ун-та. – 2011. – № 8.
3. Krone M. Heuristic programming applied to scheduling models. – Proc. 5th Annual Princeton Conf. Inform. Sci. and Syst., 1971. – P. 193-196.
4. Нейдорф Р.А., Жикулин А.А. Исследование селективно-перестановочного метода решения однородной распределительной задачи с использованием мультиперестановок // Системный анализ, управление и обработка информации: тр. 3-го Междунар семина-
ра. – Ростов-на-Дону: ИЦ ДГТУ, 2012. – С. 57-68.
5. Жикулин А.А. Метод повышения эффективности работы селективно-перестановочного алгоритма решения распределительных задач на основе эквивалентных перестановок // Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012): тр. X Междунар. науч.-технич. форума. – Ростов-на-Дону: ИЦ ДГТУ, 2012. – С. 376-381.

Comments are closed.