PLA-based permutation-scheduling

• Autorzy: Jędrzejowicz, J. , Jędrzejowicz, P.
• Języki publikacji: EN

Abstrakty

EN

The paper proposes the implementation of population learning algorithm (PLA) for solving three well-known NP-hard permutation-scheduling problems. PLA is a recently developed method belonging to the class of the population-based algorithms. One of possible applications of the PLA is solving difficult optimization problems. The first of the discussed problems involves scheduling tasks on a single machine against common due date with earliness and tardiness penalties. The second is known as the permutation flow shop problem. The third one involves scheduling tasks on a single machine with total weighted tardiness as a criterion. To evaluate the proposed implementations computational experiments have been carried. They involved solving available sets of benchmark problems and comparing the results with the optimum or best-known solutions. PLA has found better upper bounds on several benchmark instances. Experiments have also helped to identify some behavioral characteristics of the proposed algorithms.

Słowa kluczowe

PL

szeregowanie

EN

population learning algorithm; permutation scheduling problem

• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2003
• Tom: Vol. 28, No. 3
• Strony: 159-177
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Jędrzejowicz, J.

• Institute of Mathematics, Gdansk University, Wita Stwosza 57, Gdansk, Poland,

autor

Jędrzejowicz, P.

• Department of Informations Systems, Gdynia Maritime University, Morska 83, Gdynia, Poland,

Bibliografia

• [1] Biskup D., M. Feldmann., Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates, Computers & Operations Research, 28, 2001, 787-801.
• [2] Blazewicz J., K.H. Ecker, E. Pesch, G. Schmidt, J. Weglarz., Scheduling Computer and Manufacturing Processes, Springer, Berlin, 1996.
• [3] Crauwels H.A.J., C.N. Potts and L.N. Van Wassenhove., Local search heuristics for the single machine total weighted tardiness scheduling problem, Informs Journal on Computing, 10, 1998, 341-350.
• [4] Du J., J.Y. Leung., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15, 1990, 483-495.
• [5] Feldmann M., D. Biskup., Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches, Discussion Paper No 425, University of Bielefeld, Bielefeld, 1999.
• [6] Feo T.A., M.G.C. Resende., A probabilistic heuristic for computationally difficult set covering problems, Operations Research Letters, 8, 1989, 706-712.
• [7] Garey M.R., D.S. Johnson, R. Sethi., The complexity of flowshop and jobshop scheduling, Math. Oper. Res., 1, 1976, 117-129.
• [8] Glover F., Tabu search: a tutorial, Interfaces, 20, 1990, 74-94.
• [9] Hall N.G., M.E. Posner., Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date, Operations Research, 39, 1991, 836-846.
• [10] Hoogeveen J.A., S.L. Van De Velde., Scheduling around a small common due date, European Journal of Operational Research, 55, 1991, 237-242.
• [11] James R.J.W., Using tabu search to solve the common due date early/tardy machine scheduling problem, Computers & Operations Research, 24, 1997, 199-208.
• [12] Jedrzejowicz P., Social Learning Algorithm as a Tool for Solving Some Difficult Scheduling Problems, Foundation of Computing and Decision Sciences, 24, 1999, 51-66.
• [13] Jedrzejowicz J., P. Jedrzejowicz., Permutation Scheduling Using Population Learning Algorithm, in: E. Damiani et al. (eds.), Knowledge-Based Intelligent Information Engineering Systems and Allied Technologies, IOS Press, Amsterdam, 2002, 93-97.
• [14] Jedrzejowicz J., P. Jedrzejowicz., Experimental Evaluation of the PLA-Based Permutation-Scheduling, in: A. Abraham et al.(eds.) Soft Computing Systems: Design, Management and Applications, IOS Press, Amsterdam, 2002, 241-250.
• [15] Kanet J.J., Minimizing the average deviation of job completion times around a common due date, Naval Research Logistics Quarterly, 28, 1981, 643-651.
• [16] Kirkpatrick S., C.D. Gelatt Jr., M.P. Vecchi., Optimization by simulated annealing, Science, 220, 1983, 671-680.
• [17] Lee C.Y., S.J. Kim., Parallel genetic algorithms for the earliness-tardiness job scheduling problem with general penalty weights, Computers & Industrial Engineering, 28, 1995, 231-243.
• [18] Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer, Berlin, 1992.
• [19] Moscato P., Memetic Algorithms: A short introduction, in: D. Corne, M. Dorigo, F. Glover (eds.), New Ideas in Optimization, McGraw-Hill, New York, 1999, 219-234.
• [20] Reeves C., A genetic algorithm for flowshop sequencing, Computers and Operations Research, 22 (1995) 5-13.
• [21] Reynolds R.G., An Introduction to Cultural Algorithms. In: A.V. Sebald, L.J. Fogel (Eds.), Proceedings of the Third Annual Conference on Evolutionary Programming, World Scientific , River Edge, (1994) 131-139.
• [22] Taillard E., Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Operational Research, 47 (1990) 65-74.
• [23] Taillard E., Benchmarks for basic scheduling instances, European Journal of Operational Research, 64 (1993) 278-285.
• [24] Tian P., J. Ma, D.M. Zhang., Application of the simulated annealing algorithm to the combinatorial optimisation problem with permutation property: An investigation of generation mechanism, European Journal of Operational Research, 118 (1999) 81-94.