Computational Algorithms and Numerical Dimensions

Quarterly Publication

Current Issue

By Issue

By Author

By Subject

Author Index

Keyword Index

About Journal

Aims and Scope

Publication Ethics

Complaints Procedure

Peer Review Process

Open Access Policy

Related Links

FAQ

Journal Metrics

News

Editorial Board

Editor Guide in Publons

Indexing and Abstracting

A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effects

Document Type : Original Article

Authors

1 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran.

2 Department of Structural Mechanics and Analysis, Technische University Berlin, Strasse des 17. Juni 135, 10623 Berlin, Germany.

Abstract

This paper deals with the single machine scheduling problem with sequence-dependent setup time and learning effect on processing time, where the objective is to minimize total earliness and tardiness of the jobs. A Mixed Integer Linear Programming (MILP) model capable of solving small-sized problems is proposed to formulate this problem. In view of the NP-hard nature of the problem, the Hybrid Particle Swarm Optimization (HPSO) algorithm is proposed to solve the large-sized problems. In order to utilize Particle Swarm Optimization (PSO) to solve the scheduling problems, the proposed HPSO approach uses a random key representation to encode solutions, which can convert the job sequences to continuous position values. Also, the local search procedure is included within the HPSO to enhance the exploitation of the algorithm. The performance of the proposed HPSO is verified for small and medium-sized problems by comparing its results with the best solution obtained by the LINGO. In order to test the applicability of the proposed algorithm to solve large-sized problems, 120 instances are generated, and the results are compared with a Random Key Genetic Algorithm (RKGA). The results show the effectiveness of the proposed model and algorithm.

Keywords

References
[1]     Radhakrishnan, S., & Ventura, J. A. (2000). Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times. International journal of production research, 38(10), 2233–2252. DOI:10.1080/00207540050028070
[2]     Allahverdi, A., Ng, C. T., Cheng, T. C. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European journal of operational research, 187(3), 985–1032. DOI:10.1016/j.ejor.2006.06.060
[3]     Baker, K. R., & Scudder, G. D. (1990). Sequencing with earliness and tardiness penalties. A review. Operations research, 38(1), 22–36. DOI:10.1287/opre.38.1.22
[4]     M’Hallah, R. (2007). Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Computers and operations research, 34(10), 3126–3142. DOI:10.1016/j.cor.2005.11.021
[5]     Lee, C. Y., & Kim, S. J. (1995). Parallel genetic algorithms for the earliness-tardiness job scheduling problem with general penalty weights. Computers and industrial engineering, 28(2), 231–243. DOI:10.1016/0360-8352(94)00197-U
[6]     Hao, Q., Yang, Z., Wang, D., & Li, Z. (1996). Common due-date determination and sequencing using Tabu Search. Computers and operations research, 23(5), 409–417. DOI:10.1016/0305-0548(95)00051-8
[7]     James, R. J. W. (1997). Using tabu search to solve the common due date early/tardy machine scheduling problem. Computers and operations research, 24(3), 199–208. DOI:10.1016/S0305-0548(96)00052-4
[8]     Almeida, M. T., & Centeno, M. (1998). A composite heuristic for the single machine early/tardy job scheduling problem. Computers and operations research, 25(7–8), 625–635. DOI:10.1016/S0305-0548(97)00097-X
[9]     Nearchou, A. C. (2008). A differential evolution approach for the common due date early/tardy job scheduling problem. Computers and operations research, 35(4), 1329–1343. DOI:10.1016/j.cor.2006.08.013
[10]   Chang, P. C., Chen, S.-H., & Mani, V. (2007). Single machine scheduling for jobs with individual due dates and a learning effect: genetic algorithm approach single machine scheduling for jobs: genetic algorithm approach. International journal of computational science, 1(2), 215–223.
[11]   Valente, J. M. S., & Gonçalves, J. F. (2009). A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties. Computers & operations research, 36(10), 2707–2715. https://doi.org/10.1016/j.cor.2008.11.016
[12]   Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2), 154-160. DOI: 10.1287/ijoc.6.2.154
[13]   Eberhart, R., & Kennedy, J. (1995). Particle swarm optimization. Proceedings of the IEEE international conference on neural networks (Vol. 4, pp. 1942–1948). Citeseer.
[14]   Yoshida, H., Kawata, K., Fukuyama, Y., Takayama, S., & Nakanishi, Y. (2000). A particle swarm optimization for reactive power and voltage control considering voltage security assessment. IEEE transactions on power systems, 15(4), 1232–1239. https://ieeexplore.ieee.org/abstract/document/898095
[15]   Salman, A., Ahmad, I., & Al-Madani, S. (2002). Particle swarm optimization for task assignment problem. Microprocessors and microsystems, 26(8), 363–371. DOI:10.1016/S0141-9331(02)00053-4
[16]   Zhang, H., Li, H., & Tam, C. M. (2006). Particle swarm optimization for resource-constrained project scheduling. International journal of project management, 24(1), 83–92. https://doi.org/10.1016/j.ijproman.2005.06.006
[17]   Andrés, C., & Lozano, S. (2006). A particle swarm optimization algorithm for part-machine grouping. Robotics and computer-integrated manufacturing, 22(5–6), 468–474. DOI:10.1016/j.rcim.2005.11.013
[18]   Tasgetiren, M. F., Liang, Y. C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European journal of operational research, 177(3), 1930–1947. DOI:10.1016/j.ejor.2005.12.024
[19]   Choobineh, F. F., Mohebbi, E., & Khoo, H. (2006). A multi-objective tabu search for a single-machine scheduling problem with sequence-dependent setup times. European journal of operational research, 175(1), 318–337. DOI:10.1016/j.ejor.2005.04.038
[20]   Norman, B. A., & Bean, J. C. (1999). A genetic algorithm methodology for complex scheduling problems. Naval research logistics, 46(2), 199–211.
[21]   Wang, C. S., & Uzsoy, R. (2002). A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers and operations research, 29(12), 1621–1640. DOI:10.1016/S0305-0548(01)00031-4
[22]   Samanlioglu, F., Kurz, M. B., Ferrell, W. G., & Tangudu, S. (2007). A hybrid random-key genetic algorithm for a symmetric travelling salesman problem. International journal of operational research, 2(1), 47–63.
Computational Algorithms and Numerical Dimensions
Volume 2, Issue 2
June 2023
Pages 74-86
Files
Share
How to cite
Statistics