×
Barzegar, Behnam; Motameni, Homayun; Bozorgi, Hossein

Solving flexible job-shop scheduling problem using gravitational search algorithm and colored Petri net. (English) Zbl 1251.90114

J. Appl. Math. 2012, Article ID 651310, 20 p.9 (2012).
Summary: Scheduled production system leads to avoiding stock accumulations, losses reduction, decreasing or even eliminating idol machines, and effort to better benefitting from machines for on time responding customer orders and supplying requested materials in suitable time. In flexible job-shop scheduling production systems, we could reduce time and costs by transferring and delivering operations on existing machines, that is, among NP-hard problems. The scheduling objective minimizes the maximal completion time of all the operations, which is denoted by Makespan. Different methods and algorithms have been presented for solving this problem. Having a reasonable scheduled production system has significant influence on improving effectiveness and attaining to organization goals. In this paper, new algorithm were proposed for flexible job-shop scheduling problem systems (FJSSP-GSPN) that is based on gravitational search algorithm (GSA). In the proposed method, the flexible job-shop scheduling problem systems was modeled by color Petri net and CPN tool and then a scheduled job was programmed by GSA algorithm. The experimental results showed that the proposed method has reasonable performance in comparison with other algorithms.

Cited in 3 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B30 Production models

Keywords:

job-shop scheduling production systems
PDF BibTeX XML Cite
\textit{B. Barzegar} et al., J. Appl. Math. 2012, Article ID 651310, 20 p.9 (2012; Zbl 1251.90114)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] P. Brucker and R. Schlie, “Job-shop scheduling with multi-purpose machines,” Computing, vol. 45, no. 4, pp. 369-375, 1990. · Zbl 0813.90058
[2] P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Annals of Operations Research, vol. 41, no. 3, pp. 157-183, 1993. · Zbl 0775.90227
[3] A. S. Jain and S. Meeran, “Deterministic job-shop scheduling: past, present and future,” European Journal of Operational Research, vol. 113, no. 2, pp. 390-434, 1999. · Zbl 0938.90028
[4] M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research, vol. 1, no. 2, pp. 117-129, 1976. · Zbl 0396.90041
[5] H. R. Louren\cco, “Local optimization and the jobshop scheduling problem,” European Journal of Operational Research, vol. 83, no. 2, pp. 347-364, 1995.
[6] D. Sun, R. Batta, and L. Lin, “Effective job shop scheduling through active chain manipulation,” Computers and Operations Research, vol. 22, no. 2, pp. 159-172, 1995. · Zbl 0812.90072
[7] E. Nowicki and C. Smutnicki, “A fast taboo search algorithm for the job shop problem,” Management Science, vol. 42, no. 6, pp. 797-813, 1996. · Zbl 0880.90079
[8] F. Pezzella and E. Merelli, “A tabu search method guided by shifting bottleneck for the job shop scheduling problem,” European Journal of Operational Research, vol. 120, no. 2, pp. 297-310, 2000. · Zbl 0953.90026
[9] J. Bean, “Genetic algorithms and random keys for sequencing and optimization,” Journal on Computing, vol. 6, pp. 154-160, 1994. · Zbl 0807.90060
[10] S. Kobayashi, I. Ono, and M. Yamamura, “An efficient genetic algorithm for job shop scheduling problems,” in Proceedings of the 6th International Conference on Genetic Algorithms, L. J. Eshelman, Ed., pp. 506-511, Morgan Kaufman, San Francisco, Calif, USA, 1995.
[11] J. F. Gon\ccalves, J. J. M. Mendes, and M. G. C. Resende, “A hybrid genetic algorithm for the job shop scheduling problem,” European Journal of Operational Research, vol. 167, no. 1, pp. 77-95, 2005. · Zbl 1075.90028
[12] L. Wang and D.-Z. Zheng, “An effective hybrid optimization strategy for job-shop scheduling problems,” Computers & Operations Research, vol. 28, no. 6, pp. 585-596, 2001. · Zbl 1017.90048
[13] P. Fattahi, M. Saidi Mehrabad, and F. Jolai, “Mathematical modeling and heuristic approaches to flexible job shop scheduling problems,” Journal of Intelligent Manufacturing, vol. 18, no. 3, pp. 331-342, 2007.
[14] I. C. Choi and D. S. Choi, “A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups,” Computers and Industrial Engineering, vol. 42, no. 1, pp. 43-58, 2002.
[15] W. Xia and Z. Wu, “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems,” Computers and Industrial Engineering, vol. 48, no. 2, pp. 409-425, 2005.
[16] M. Mastrolilli and L. M. Gambardella, “Effective neighbourhood functions for the flexible job shop problem,” Journal of Scheduling, vol. 3, no. 1, pp. 3-20, 2000. · Zbl 1028.90018
[17] F. Pezzella, G. Morganti, and G. Ciaschetti, “A genetic algorithm for the flexible job-shop scheduling problem,” Computers and Operations Research, vol. 35, no. 10, pp. 3202-3212, 2008. · Zbl 1162.90014
[18] J. Gao, L. Sun, and M. Gen, “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,” Computers & Operations Research, vol. 35, no. 9, pp. 2892-2907, 2008. · Zbl 1144.90379
[19] M. Yazdani, M. Amiri, and M. Zandieh, “Flexible job-shop scheduling with parallel variable neighborhood search algorithm,” Expert Systems with Applications, vol. 37, no. 1, pp. 678-687, 2010. · Zbl 1197.90191
[20] F. M. Defersha and M. Chen, “A coarse-grain parallel genetic algorithm for flexible job-shop scheduling with lot streaming,” in Proceedings of the International Conference on Computational Science and Engineering (CSE ’09), pp. 201-208, August 2009.
[21] T. Murata, “Petri nets: properties, analysis and applications,” Proceedings of the IEEE, vol. 77, no. 4, pp. 541-580, 1989.
[22] B. Berthomieu and M. Diaz, “Modeling and verification of time dependent systems using time Petri nets,” IEEE Transactions on Software Engineering, vol. 17, no. 3, pp. 259-273, 1991. · Zbl 05113493
[23] K. Jensen, Coloured Petri Nets Vol. 1: Basic Concepts, EATCS Monographs on Theoretical Computer Science, Springer, Berlin, Germany, 1992. · Zbl 0762.68004
[24] K. Jensen, L. M. Kristensen, and L. Wells, “Coloured Petri nets and CPN tools for modelling and validation of concurrent systems,” International Journal of Software Tools Technology Transfer, vol. 9, no. 3, pp. 213-254, 2007. · Zbl 05193087
[25] E. Nowicki and C. Smutnicki, “A fast taboo search algorithm for the job shop problem,” Management Science, vol. 42, no. 6, pp. 797-813, 1996. · Zbl 0880.90079
[26] F. Pezzella and E. Merelli, “A tabu search method guided by shifting bottleneck for the job shop scheduling problem,” European Journal of Operational Research, vol. 120, no. 2, pp. 297-310, 2000. · Zbl 0953.90026
[27] I. Sabuncuoglu and M. Bayiz, “Job shop scheduling with beam search,” European Journal of Operational Research, vol. 118, no. 2, pp. 390-412, 1999. · Zbl 0940.90037
[28] H. W. Ge, L. Sun, Y. C. Liang, and F. Qian, “An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling,” IEEE Transactions on Systems, Man, and Cybernetics Part A, vol. 38, no. 2, pp. 358-368, 2008.
[29] C. Rego and R. Duarte, “A filter-and-fan approach to the job shop scheduling problem,” European Journal of Operational Research, vol. 194, no. 3, pp. 650-662, 2009. · Zbl 1162.90016
[30] S. Cun-li, L. Xiao-bing, W. Wei, and B. Xin, “A hybrid particle swarm optimization algorithm for job-shop scheduling problem,” International Journal of Advancements in Computing Technology, vol. 3, no. 4, 2011.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.