• Previous Article
    Multi-criteria media mix decision model for advertising a single product with segment specific and mass media
  • JIMO Home
  • This Issue
  • Next Article
    Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set
2016, 12(4): 1391-1415. doi: 10.3934/jimo.2016.12.1391

A priority-based genetic algorithm for a flexible job shop scheduling problem

1. 

Department of Industrial Engineering, İstanbul Technical University, 34367 İstanbul, Turkey, Turkey

2. 

ALGORITMI Research Centre, University of Minho, Campus Azurem, 4800-058 Guimarães, Portugal

3. 

Center for Applied Optimization Department of Industrial and Systems Engineering, University of Florida, 32611

Received  January 2015 Revised  June 2015 Published  January 2016

In this study, a genetic algorithm (GA) with priority-based representation is proposed for a flexible job shop scheduling problem (FJSP) which is one of the hardest operations research problems. Investigating the effect of the proposed representation schema on FJSP is the main contribution to the literature. The priority of each operation is represented by a gene on the chromosome which is used by a constructive algorithm performed for decoding. All active schedules, which constitute a subset of feasible schedules including the optimal, can be generated by the constructive algorithm. To obtain improved solutions, iterated local search (ILS) is applied to the chromosomes at the end of each reproduction process. The most widely used FJSP data sets generated in the literature are used for benchmarking and evaluating the performance of the proposed GA methodology. The computational results show that the proposed GA performed at the same level or better with respect to the makespan for some data sets when compared to the results from the literature.
Citation: Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
References:
[1]

N. Al-Hinai and T. Y. ElMekkawy, An efficient hybridized genetic algorithm architecture for the flexible job shop scheduling problem,, Flexible Services and Manufacturing Journal, 23 (2011), 64. doi: 10.1007/s10696-010-9067-y.

[2]

M. Amiri, M. Zandieh, M. Yazdani and A. Bagheri, A variable neighbourhood search algorithm for the flexible job-shop scheduling problem,, International Journal of Production Research, 48 (2010), 5671. doi: 10.1080/00207540903055743.

[3]

J. Arroyo, G. Nunes and E. Kamke, Iterative local search heuristic for the single machine scheduling problem with sequence dependent setup times and due dates,, in Hybrid Intelligent Systems, 1 (2009), 505. doi: 10.1109/HIS.2009.104.

[4]

A. Bagheri, M. Zandieh, I. Mahdavi and M. Yazdani, An artificial immune algorithm for the flexible job-shop scheduling problem,, Future Generation Computer Systems-the International Journal of Grid Computing-Theory Methods and Applications, 26 (2010), 533. doi: 10.1016/j.future.2009.10.004.

[5]

A. Baykasoglu, Linguistic-based meta-heuristic optimization model for flexible job shop scheduling,, International Journal of Production Research, 40 (2002), 4523. doi: 10.1080/00207540210147043.

[6]

A. Baykasoglu, L. Ozbakir and A. I. Sonmez, Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems,, Journal of Intelligent Manufacturing, 15 (2004), 777. doi: 10.1023/B:JIMS.0000042663.16199.84.

[7]

J. E. Beasley, Population heuristics,, in Handbook of Applied Optimization (eds. P. M. Pardalos and M. G. Resende), (2002). doi: 10.1007/978-1-4757-5362-2.

[8]

D. Behnke and M. J. Geiger, Test Instances for the Flexible Job Shop Scheduling Problem with Work Centers,, Technical report, (2012).

[9]

W. Bozejko, M. Uchronski and M. Wodecki, Parallel hybrid metaheuristics for the flexible job shop problem,, Computers and Industrial Engineering, 59 (2010), 323. doi: 10.1016/j.cie.2010.05.004.

[10]

P. Brandimarte, Routing and scheduling in a flexible job shop by tabu search,, Annals of Operations Research, 41 (1993), 157.

[11]

P. Brucker and R. Schlie, Job-shop scheduling with multipurpose machines,, Computing, 45 (1990), 369. doi: 10.1007/BF02238804.

[12]

M. Caramia and P. Dell'Olmo, Coloring graphs by iterated local search traversing feasible and infeasible solutions,, Discrete Applied Mathematics, 156 (2008), 201. doi: 10.1016/j.dam.2006.07.013.

[13]

J. B. Chambers and J. W. Barnes, Flexible job shop scheduling by tabu search,, 1996., ().

[14]

Y.-L. Chang and R. S. Sullivan, Schedule generation in a dynamic job shop,, International Journal of Production Research, 28 (1990), 65. doi: 10.1080/00207549008942684.

[15]

H. Chen, J. Ihlow and C. Lehmann, A genetic algorithm for flexible job-shop scheduling,, in Robotics and Automation, 2 (1999), 1120. doi: 10.1109/ROBOT.1999.772512.

[16]

T.-C. Chiang and H.-J. Lin, A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling,, International Journal of Production Economics, 141 (2013), 87. doi: 10.1016/j.ijpe.2012.03.034.

[17]

J.-F. Cordeau, G. Laporte and F. Pasin, An iterated local search heuristic for the logistics network design problem with single assignment,, International Journal of Production Economics, 113 (2008), 626. doi: 10.1016/j.ijpe.2007.10.015.

[18]

M. den Besten, T. Stützle and M. Dorigo, Design of iterated local search algorithms,, in Applications of Evolutionary Computing (ed. E. Boers), (2037), 441. doi: 10.1007/3-540-45365-2_46.

[19]

I. Driss, K. Mouss and A. Laggoun, A new genetic algorithm for flexible job-shop scheduling problems,, Journal of Mechanical Science and Technology, 29 (2015), 1273. doi: 10.1007/s12206-015-0242-7.

[20]

M. Ennigrou and K. Ghedira, New local diversification techniques for flexible job shop scheduling problem with a multi-agent approach,, Autonomous Agents and Multi-Agent Systems, 17 (2008), 270. doi: 10.1007/s10458-008-9031-3.

[21]

I. Essafi, Y. Mati and S. Dauzère-P\'erès, A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,, Computers & Operations Research, 35 (2008), 2599. doi: 10.1016/j.cor.2006.12.019.

[22]

H. Farughi, B. Yousefi Yegane and M. Fathian, A new critical path method and a memetic algorithm for flexible job shop scheduling with overlapping operations,, Simulation, 89 (2013), 264.

[23]

P. Fattahi, M. S. Mehrabad and F. Jolai, Mathematical modeling and heuristic approaches to flexible job shop scheduling problems,, Journal of Intelligent Manufacturing, 18 (2007), 331. doi: 10.1007/s10845-007-0026-8.

[24]

M. Frutos, A. C. Olivera and F. Tohme, A memetic algorithm based on a NSGAII scheme for the flexible job-shop scheduling problem,, Annals of Operations Research, 181 (2010), 745. doi: 10.1007/s10479-010-0751-9.

[25]

J. Gao, M. Gen and L. Y. Sun, Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm,, Journal of Intelligent Manufacturing, 17 (2006), 493. doi: 10.1007/s10845-005-0021-x.

[26]

J. Gao, M. Gen, L. Y. Sun and X. H. Zhao, A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems,, Computers and Industrial Engineering, 53 (2007), 149. doi: 10.1016/j.cie.2007.04.010.

[27]

J. Gao, L. Y. Sun and M. S. Gen, A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,, Computers and Operations Research, 35 (2008), 2892. doi: 10.1016/j.cor.2007.01.001.

[28]

K. Gao, P. Suganthan, Q. Pan, T. Chua, T. Cai and C. Chong, Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling,, Information Sciences, 289 (2014), 76. doi: 10.1016/j.ins.2014.07.039.

[29]

L. Gao, C. Y. Zhang and X. J. Wang, An improved genetic algorithm for multi-objective flexible job-shop scheduling problem,, Advanced Materials Research, 97 (2010), 2449.

[30]

M. R. Garey, D. S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling,, Mathematics of Operations Research, 1 (1976), 117. doi: 10.1287/moor.1.2.117.

[31]

B. Giffler and G. Thompson, Algorithms for solving production scheduling problems,, Operations Research, 8 (1960), 487. doi: 10.1287/opre.8.4.487.

[32]

D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning,, Addison-Wesley, (1989).

[33]

R. Graham, E. Lawler, J. Lenstra and A. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics, 5 (1979), 287. doi: 10.1016/S0167-5060(08)70356-X.

[34]

J. Grobler, A. P. Engelbrecht, S. Kok and S. Yadavalli, Metaheuristics for the multi-objective fjsp with sequence-dependent set-up times, auxiliary resources and machine down time,, Annals of Operations Research, 180 (2010), 165. doi: 10.1007/s10479-008-0501-4.

[35]

H. Hashimoto, M. Yagiura and T. Ibaraki, An iterated local search algorithm for the time-dependent vehicle routing problem with time windows,, Discrete Optimization, 5 (2008), 434. doi: 10.1016/j.disopt.2007.05.004.

[36]

N. B. Ho, J. C. Tay and E. M. K. Lai, An effective architecture for learning and evolving flexible job-shop schedules,, European Journal of Operational Research, 179 (2007), 316. doi: 10.1016/j.ejor.2006.04.007.

[37]

J. Hurink, B. Jurisch and M. Thole, Tabu search for the job-shop scheduling problem with multi-purpose machines,, OR Spectrum, 15 (1994), 205. doi: 10.1007/BF01719451.

[38]

A. S. Jain and S. Meeran, Deterministic job-shop scheduling: Past, present and future,, European Journal of Operational Research, 113 (1999), 390. doi: 10.1016/S0377-2217(98)00113-1.

[39]

H. Jia, A. Nee, J. Fuh and Y. Zhang, A modified genetic algorithm for distributed scheduling problems,, Journal of Intelligent Manufacturing, 14 (2003), 351.

[40]

S. Jia and Z.-H. Hu, Path-relinking tabu search for the multi-objective flexible job shop scheduling problem,, Computers & Operations Research, 47 (2014), 11. doi: 10.1016/j.cor.2014.01.010.

[41]

I. Kacem, S. Hammadi and P. Borne, Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,, Ieee Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 32 (2002), 1. doi: 10.1109/TSMCC.2002.1009117.

[42]

I. Kacem, S. Hammadi and P. Borne, Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic,, Mathematics and Computers in Simulation, 60 (2002), 245. doi: 10.1016/S0378-4754(02)00019-8.

[43]

H. Karimi, S. H. A. Rahmati and M. Zandieh, An efficient knowledge-based algorithm for the flexible job shop scheduling problem,, Knowledge-Based Systems, 36 (2012), 236. doi: 10.1016/j.knosys.2012.04.001.

[44]

S. Karthikeyan, P. Asokan and S. Nickolas, A hybrid discrete firefly algorithm for multi-objective flexible job shop scheduling problem with limited resource constraints,, The International Journal of Advanced Manufacturing Technology, 72 (2014), 1567. doi: 10.1007/s00170-014-5753-3.

[45]

C.-Y. Lee and M. Pinedo, Optimization and heuristics in scheduling,, in Handbook of Applied Optimization (eds. P. M. Pardalos and M. G. Resende), (2002), 569.

[46]

J. Li, Q. Pan, S. Xie and S. Wang, A hybrid artificial bee colony algorithm for flexible job shop scheduling problems,, International Journal of Computers Communications and Control, 6 (2011), 286.

[47]

J. Q. Li, Q. K. Pan and Y. C. Liang, An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems,, Computers and Industrial Engineering, 59 (2010), 647. doi: 10.1016/j.cie.2010.07.014.

[48]

J. Q. Li, Q. K. Pan, P. N. Suganthan and T. J. Chua, A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem,, International Journal of Advanced Manufacturing Technology, 52 (2011), 683. doi: 10.1007/s00170-010-2743-y.

[49]

J. Q. Li, Q. K. Pan and S. X. Xie, A hybrid variable neighborhood search algorithm for solving multi-objective flexible job shop problems,, Computer Science and Information Systems, 7 (2010), 907. doi: 10.2298/CSIS090608017L.

[50]

J.-Q. Li, Q.-K. Pan and M. F. Tasgetiren, A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities,, Applied Mathematical Modelling, 38 (2014), 1111. doi: 10.1016/j.apm.2013.07.038.

[51]

N. Liouane, I. Saad, S. Hammadi and P. Borne, Ant systems and local search optimization for flexible job shop scheduling production,, International Journal of Computers Communications and Control, 2 (2007), 174.

[52]

H. Lourenço, O. Martin and T. Stützle, Iterated local search,, in Handbook of Metaheuristics (eds. F. Glover and G. Kochenberger), (2003), 320.

[53]

H. Lourenço, O. Martin and T. Stützle, Iterated local search: Framework and applications,, in Handbook of Metaheuristics (eds. M. Gendreau and J.-Y. Potvin), (2010), 363.

[54]

M. Mastrolilli and L. Gambardella, Effective neighborhood functions for the flexible job shop problem,, Journal of Scheduling, 3 (2000), 3. doi: 10.1002/(SICI)1099-1425(200001/02)3:1<3::AID-JOS32>3.0.CO;2-Y.

[55]

Z. Michalewicz and D. Fogel, How to Solve It: Modern Heuristics,, Springer-Verlag, (2000). doi: 10.1007/978-3-662-04131-4.

[56]

E. Moradi, S. Ghomi and M. Zandieh, An efficient architecture for scheduling flexible job-shop with machine availability constraints,, International Journal of Advanced Manufacturing Technology, 51 (2010), 325. doi: 10.1007/s00170-010-2621-7.

[57]

E. Moradi, S. Ghomi and M. Zandieh, Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem,, Expert Systems with Applications, 38 (2011), 7169. doi: 10.1016/j.eswa.2010.12.043.

[58]

G. Moslehi and M. Mahnam, A pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search,, International Journal of Production Economics, 129 (2011), 14. doi: 10.1016/j.ijpe.2010.08.004.

[59]

M. Mousakhani, Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness,, International Journal of Production Research, 51 (2013), 3476. doi: 10.1080/00207543.2012.746480.

[60]

M. A. Nascimento, Giffler and thompson's algorithm for job shop scheduling is still good for flexible manufacturing systems,, The Journal of the Operational Research Society, 44 (1993), 521.

[61]

J. A. Oliveira, L. Dias and G. Pereira, Solving the job shop problem with a random keys genetic algorithm with instance parameters,, in 2nd International Conference on Engineering Optimization, (2010).

[62]

I. Ono, M. Yamamura and S. Kobayashi, A genetic algorithm for job-shop scheduling problems using job-based order crossover,, in Evolutionary Computation, (1996), 547. doi: 10.1109/ICEC.1996.542658.

[63]

L. Paquete and T. Stützle, An experimental investigation of iterated local search for coloring graphs,, in Applications of Evolutionary Computing (eds. S. Cagnoni, (2279), 122.

[64]

P. M. Pardalos and O. V. Shylo, An algorithm for the job shop scheduling problem based on global equilibrium search techniques,, Computational Management Science, 3 (2006), 331. doi: 10.1007/s10287-006-0023-y.

[65]

F. Pezzella, G. Morganti and G. Ciaschetti, A genetic algorithm for the flexible job-shop scheduling problem,, Computers and Operations Research, 35 (2008), 3202. doi: 10.1016/j.cor.2007.02.014.

[66]

S. Rahmati, M. Zandieh and M. Yazdani, Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem,, The International Journal of Advanced Manufacturing Technology, 64 (2013), 915. doi: 10.1007/s00170-012-4051-1.

[67]

M. Rajkumar, P. Asokan, N. Anilkumar and T. Page, A grasp algorithm for flexible job-shop scheduling problem with limited resource constraints,, International Journal of Production Research, 49 (2011), 2409. doi: 10.1080/00207541003709544.

[68]

M. Rohaninejad, A. Kheirkhah, P. Fattahi and B. Vahedi-Nouri, A hybrid multi-objective genetic algorithm based on the electre method for a capacitated flexible job shop scheduling problem,, The International Journal of Advanced Manufacturing Technology, 77 (2015), 51. doi: 10.1007/s00170-014-6415-1.

[69]

V. Roshanaei, A. Azab and H. ElMaraghy, Mathematical modelling and a meta-heuristic for flexible job shop scheduling,, International Journal of Production Research, 51 (2013), 6247. doi: 10.1080/00207543.2013.827806.

[70]

C. R. Schrich, V. A. Armentano and M. Laguna, Tardiness minimization in a flexible job shop: A tabu search approach,, Journal of Intelligent Manufacturing, 15 (2004), 103.

[71]

X. Shao, W. Liu, Q. Liu and C. Zhang, Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem,, The International Journal of Advanced Manufacturing Technology, 67 (2013), 2885. doi: 10.1007/s00170-012-4701-3.

[72]

T. Stützle, Iterated local search for the quadratic assignment problem,, European Journal of Operational Research, 174 (2006), 1519. doi: 10.1016/j.ejor.2005.01.066.

[73]

L. Tang and X. Wang, Iterated local search algorithm based on very large-scale neighborhood for prize-collecting vehicle routing problem,, The International Journal of Advanced Manufacturing Technology, 29 (2006), 1246. doi: 10.1007/s00170-005-0014-0.

[74]

J. C. Tay and N. B. Ho, Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems,, Computers and Industrial Engineering, 54 (2008), 453. doi: 10.1016/j.cie.2007.08.008.

[75]

S. J. Wang, B. H. Zhou and L. F. Xi, A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem,, International Journal of Production Research, 46 (2008), 3027.

[76]

X. J. Wang, L. Gao, C. Y. Zhang and X. Y. Shao, A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem,, International Journal of Advanced Manufacturing Technology, 51 (2010), 757. doi: 10.1007/s00170-010-2642-2.

[77]

Y. Wang, H. Yin and K. Qin, A novel genetic algorithm for flexible job shop scheduling problems with machine disruptions,, The International Journal of Advanced Manufacturing Technology, 68 (2013), 1317. doi: 10.1007/s00170-013-4923-z.

[78]

W. J. Xia and Z. M. Wu, An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems,, Computers and Industrial Engineering, 48 (2005), 409. doi: 10.1016/j.cie.2005.01.018.

[79]

L. N. Xing, Y. W. Chen and K. W. Yang, Multi-population interactive coevolutionary algorithm for flexible job shop scheduling problems,, Computational Optimization and Applications, 48 (2011), 139. doi: 10.1007/s10589-009-9244-7.

[80]

M. Yazdani, M. Amiri and M. Zandieh, Flexible job-shop scheduling with parallel variable neighborhood search algorithm,, Expert Systems with Applications, 37 (2010), 678. doi: 10.1016/j.eswa.2009.06.007.

[81]

Y. Yuan and H. Xu, Flexible job shop scheduling using hybrid differential evolution algorithms,, Computers & Industrial Engineering, 65 (2013), 246. doi: 10.1016/j.cie.2013.02.022.

[82]

Y. Yuan and H. Xu, An integrated search heuristic for large-scale flexible job shop scheduling problems,, Computers & Operations Research, 40 (2013), 2864. doi: 10.1016/j.cor.2013.06.010.

[83]

Y. Yuan and H. Xu, Multiobjective flexible job shop scheduling using memetic algorithms,, Automation Science and Engineering, 12 (2015), 336. doi: 10.1109/TASE.2013.2274517.

[84]

Y. Yuan, H. Xu and J. Yang, A hybrid harmony search algorithm for the flexible job shop scheduling problem,, Applied Soft Computing, 13 (2013), 3259. doi: 10.1016/j.asoc.2013.02.013.

[85]

G. H. Zhang, X. Y. Shao, P. G. Li and L. Gao, An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem,, Computers and Industrial Engineering, 56 (2009), 1309. doi: 10.1016/j.cie.2008.07.021.

[86]

Q. Zhang and J. Sun, Iterated local search with guided mutation,, 2006 IEEE International Conference on Evolutionary Computation, (): 924.

[87]

M. Ziaee, A heuristic algorithm for solving flexible job shop scheduling problem,, The International Journal of Advanced Manufacturing Technology, 71 (2014), 519. doi: 10.1007/s00170-013-5510-z.

[88]

N. Zribi, I. Kacem, A. El Kamel and P. Borne, Assignment and scheduling in flexible job-shops by hierarchical optimization,, Ieee Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 37 (2007), 652. doi: 10.1109/TSMCC.2007.897494.

show all references

References:
[1]

N. Al-Hinai and T. Y. ElMekkawy, An efficient hybridized genetic algorithm architecture for the flexible job shop scheduling problem,, Flexible Services and Manufacturing Journal, 23 (2011), 64. doi: 10.1007/s10696-010-9067-y.

[2]

M. Amiri, M. Zandieh, M. Yazdani and A. Bagheri, A variable neighbourhood search algorithm for the flexible job-shop scheduling problem,, International Journal of Production Research, 48 (2010), 5671. doi: 10.1080/00207540903055743.

[3]

J. Arroyo, G. Nunes and E. Kamke, Iterative local search heuristic for the single machine scheduling problem with sequence dependent setup times and due dates,, in Hybrid Intelligent Systems, 1 (2009), 505. doi: 10.1109/HIS.2009.104.

[4]

A. Bagheri, M. Zandieh, I. Mahdavi and M. Yazdani, An artificial immune algorithm for the flexible job-shop scheduling problem,, Future Generation Computer Systems-the International Journal of Grid Computing-Theory Methods and Applications, 26 (2010), 533. doi: 10.1016/j.future.2009.10.004.

[5]

A. Baykasoglu, Linguistic-based meta-heuristic optimization model for flexible job shop scheduling,, International Journal of Production Research, 40 (2002), 4523. doi: 10.1080/00207540210147043.

[6]

A. Baykasoglu, L. Ozbakir and A. I. Sonmez, Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems,, Journal of Intelligent Manufacturing, 15 (2004), 777. doi: 10.1023/B:JIMS.0000042663.16199.84.

[7]

J. E. Beasley, Population heuristics,, in Handbook of Applied Optimization (eds. P. M. Pardalos and M. G. Resende), (2002). doi: 10.1007/978-1-4757-5362-2.

[8]

D. Behnke and M. J. Geiger, Test Instances for the Flexible Job Shop Scheduling Problem with Work Centers,, Technical report, (2012).

[9]

W. Bozejko, M. Uchronski and M. Wodecki, Parallel hybrid metaheuristics for the flexible job shop problem,, Computers and Industrial Engineering, 59 (2010), 323. doi: 10.1016/j.cie.2010.05.004.

[10]

P. Brandimarte, Routing and scheduling in a flexible job shop by tabu search,, Annals of Operations Research, 41 (1993), 157.

[11]

P. Brucker and R. Schlie, Job-shop scheduling with multipurpose machines,, Computing, 45 (1990), 369. doi: 10.1007/BF02238804.

[12]

M. Caramia and P. Dell'Olmo, Coloring graphs by iterated local search traversing feasible and infeasible solutions,, Discrete Applied Mathematics, 156 (2008), 201. doi: 10.1016/j.dam.2006.07.013.

[13]

J. B. Chambers and J. W. Barnes, Flexible job shop scheduling by tabu search,, 1996., ().

[14]

Y.-L. Chang and R. S. Sullivan, Schedule generation in a dynamic job shop,, International Journal of Production Research, 28 (1990), 65. doi: 10.1080/00207549008942684.

[15]

H. Chen, J. Ihlow and C. Lehmann, A genetic algorithm for flexible job-shop scheduling,, in Robotics and Automation, 2 (1999), 1120. doi: 10.1109/ROBOT.1999.772512.

[16]

T.-C. Chiang and H.-J. Lin, A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling,, International Journal of Production Economics, 141 (2013), 87. doi: 10.1016/j.ijpe.2012.03.034.

[17]

J.-F. Cordeau, G. Laporte and F. Pasin, An iterated local search heuristic for the logistics network design problem with single assignment,, International Journal of Production Economics, 113 (2008), 626. doi: 10.1016/j.ijpe.2007.10.015.

[18]

M. den Besten, T. Stützle and M. Dorigo, Design of iterated local search algorithms,, in Applications of Evolutionary Computing (ed. E. Boers), (2037), 441. doi: 10.1007/3-540-45365-2_46.

[19]

I. Driss, K. Mouss and A. Laggoun, A new genetic algorithm for flexible job-shop scheduling problems,, Journal of Mechanical Science and Technology, 29 (2015), 1273. doi: 10.1007/s12206-015-0242-7.

[20]

M. Ennigrou and K. Ghedira, New local diversification techniques for flexible job shop scheduling problem with a multi-agent approach,, Autonomous Agents and Multi-Agent Systems, 17 (2008), 270. doi: 10.1007/s10458-008-9031-3.

[21]

I. Essafi, Y. Mati and S. Dauzère-P\'erès, A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,, Computers & Operations Research, 35 (2008), 2599. doi: 10.1016/j.cor.2006.12.019.

[22]

H. Farughi, B. Yousefi Yegane and M. Fathian, A new critical path method and a memetic algorithm for flexible job shop scheduling with overlapping operations,, Simulation, 89 (2013), 264.

[23]

P. Fattahi, M. S. Mehrabad and F. Jolai, Mathematical modeling and heuristic approaches to flexible job shop scheduling problems,, Journal of Intelligent Manufacturing, 18 (2007), 331. doi: 10.1007/s10845-007-0026-8.

[24]

M. Frutos, A. C. Olivera and F. Tohme, A memetic algorithm based on a NSGAII scheme for the flexible job-shop scheduling problem,, Annals of Operations Research, 181 (2010), 745. doi: 10.1007/s10479-010-0751-9.

[25]

J. Gao, M. Gen and L. Y. Sun, Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm,, Journal of Intelligent Manufacturing, 17 (2006), 493. doi: 10.1007/s10845-005-0021-x.

[26]

J. Gao, M. Gen, L. Y. Sun and X. H. Zhao, A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems,, Computers and Industrial Engineering, 53 (2007), 149. doi: 10.1016/j.cie.2007.04.010.

[27]

J. Gao, L. Y. Sun and M. S. Gen, A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,, Computers and Operations Research, 35 (2008), 2892. doi: 10.1016/j.cor.2007.01.001.

[28]

K. Gao, P. Suganthan, Q. Pan, T. Chua, T. Cai and C. Chong, Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling,, Information Sciences, 289 (2014), 76. doi: 10.1016/j.ins.2014.07.039.

[29]

L. Gao, C. Y. Zhang and X. J. Wang, An improved genetic algorithm for multi-objective flexible job-shop scheduling problem,, Advanced Materials Research, 97 (2010), 2449.

[30]

M. R. Garey, D. S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling,, Mathematics of Operations Research, 1 (1976), 117. doi: 10.1287/moor.1.2.117.

[31]

B. Giffler and G. Thompson, Algorithms for solving production scheduling problems,, Operations Research, 8 (1960), 487. doi: 10.1287/opre.8.4.487.

[32]

D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning,, Addison-Wesley, (1989).

[33]

R. Graham, E. Lawler, J. Lenstra and A. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics, 5 (1979), 287. doi: 10.1016/S0167-5060(08)70356-X.

[34]

J. Grobler, A. P. Engelbrecht, S. Kok and S. Yadavalli, Metaheuristics for the multi-objective fjsp with sequence-dependent set-up times, auxiliary resources and machine down time,, Annals of Operations Research, 180 (2010), 165. doi: 10.1007/s10479-008-0501-4.

[35]

H. Hashimoto, M. Yagiura and T. Ibaraki, An iterated local search algorithm for the time-dependent vehicle routing problem with time windows,, Discrete Optimization, 5 (2008), 434. doi: 10.1016/j.disopt.2007.05.004.

[36]

N. B. Ho, J. C. Tay and E. M. K. Lai, An effective architecture for learning and evolving flexible job-shop schedules,, European Journal of Operational Research, 179 (2007), 316. doi: 10.1016/j.ejor.2006.04.007.

[37]

J. Hurink, B. Jurisch and M. Thole, Tabu search for the job-shop scheduling problem with multi-purpose machines,, OR Spectrum, 15 (1994), 205. doi: 10.1007/BF01719451.

[38]

A. S. Jain and S. Meeran, Deterministic job-shop scheduling: Past, present and future,, European Journal of Operational Research, 113 (1999), 390. doi: 10.1016/S0377-2217(98)00113-1.

[39]

H. Jia, A. Nee, J. Fuh and Y. Zhang, A modified genetic algorithm for distributed scheduling problems,, Journal of Intelligent Manufacturing, 14 (2003), 351.

[40]

S. Jia and Z.-H. Hu, Path-relinking tabu search for the multi-objective flexible job shop scheduling problem,, Computers & Operations Research, 47 (2014), 11. doi: 10.1016/j.cor.2014.01.010.

[41]

I. Kacem, S. Hammadi and P. Borne, Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,, Ieee Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 32 (2002), 1. doi: 10.1109/TSMCC.2002.1009117.

[42]

I. Kacem, S. Hammadi and P. Borne, Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic,, Mathematics and Computers in Simulation, 60 (2002), 245. doi: 10.1016/S0378-4754(02)00019-8.

[43]

H. Karimi, S. H. A. Rahmati and M. Zandieh, An efficient knowledge-based algorithm for the flexible job shop scheduling problem,, Knowledge-Based Systems, 36 (2012), 236. doi: 10.1016/j.knosys.2012.04.001.

[44]

S. Karthikeyan, P. Asokan and S. Nickolas, A hybrid discrete firefly algorithm for multi-objective flexible job shop scheduling problem with limited resource constraints,, The International Journal of Advanced Manufacturing Technology, 72 (2014), 1567. doi: 10.1007/s00170-014-5753-3.

[45]

C.-Y. Lee and M. Pinedo, Optimization and heuristics in scheduling,, in Handbook of Applied Optimization (eds. P. M. Pardalos and M. G. Resende), (2002), 569.

[46]

J. Li, Q. Pan, S. Xie and S. Wang, A hybrid artificial bee colony algorithm for flexible job shop scheduling problems,, International Journal of Computers Communications and Control, 6 (2011), 286.

[47]

J. Q. Li, Q. K. Pan and Y. C. Liang, An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems,, Computers and Industrial Engineering, 59 (2010), 647. doi: 10.1016/j.cie.2010.07.014.

[48]

J. Q. Li, Q. K. Pan, P. N. Suganthan and T. J. Chua, A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem,, International Journal of Advanced Manufacturing Technology, 52 (2011), 683. doi: 10.1007/s00170-010-2743-y.

[49]

J. Q. Li, Q. K. Pan and S. X. Xie, A hybrid variable neighborhood search algorithm for solving multi-objective flexible job shop problems,, Computer Science and Information Systems, 7 (2010), 907. doi: 10.2298/CSIS090608017L.

[50]

J.-Q. Li, Q.-K. Pan and M. F. Tasgetiren, A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities,, Applied Mathematical Modelling, 38 (2014), 1111. doi: 10.1016/j.apm.2013.07.038.

[51]

N. Liouane, I. Saad, S. Hammadi and P. Borne, Ant systems and local search optimization for flexible job shop scheduling production,, International Journal of Computers Communications and Control, 2 (2007), 174.

[52]

H. Lourenço, O. Martin and T. Stützle, Iterated local search,, in Handbook of Metaheuristics (eds. F. Glover and G. Kochenberger), (2003), 320.

[53]

H. Lourenço, O. Martin and T. Stützle, Iterated local search: Framework and applications,, in Handbook of Metaheuristics (eds. M. Gendreau and J.-Y. Potvin), (2010), 363.

[54]

M. Mastrolilli and L. Gambardella, Effective neighborhood functions for the flexible job shop problem,, Journal of Scheduling, 3 (2000), 3. doi: 10.1002/(SICI)1099-1425(200001/02)3:1<3::AID-JOS32>3.0.CO;2-Y.

[55]

Z. Michalewicz and D. Fogel, How to Solve It: Modern Heuristics,, Springer-Verlag, (2000). doi: 10.1007/978-3-662-04131-4.

[56]

E. Moradi, S. Ghomi and M. Zandieh, An efficient architecture for scheduling flexible job-shop with machine availability constraints,, International Journal of Advanced Manufacturing Technology, 51 (2010), 325. doi: 10.1007/s00170-010-2621-7.

[57]

E. Moradi, S. Ghomi and M. Zandieh, Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem,, Expert Systems with Applications, 38 (2011), 7169. doi: 10.1016/j.eswa.2010.12.043.

[58]

G. Moslehi and M. Mahnam, A pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search,, International Journal of Production Economics, 129 (2011), 14. doi: 10.1016/j.ijpe.2010.08.004.

[59]

M. Mousakhani, Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness,, International Journal of Production Research, 51 (2013), 3476. doi: 10.1080/00207543.2012.746480.

[60]

M. A. Nascimento, Giffler and thompson's algorithm for job shop scheduling is still good for flexible manufacturing systems,, The Journal of the Operational Research Society, 44 (1993), 521.

[61]

J. A. Oliveira, L. Dias and G. Pereira, Solving the job shop problem with a random keys genetic algorithm with instance parameters,, in 2nd International Conference on Engineering Optimization, (2010).

[62]

I. Ono, M. Yamamura and S. Kobayashi, A genetic algorithm for job-shop scheduling problems using job-based order crossover,, in Evolutionary Computation, (1996), 547. doi: 10.1109/ICEC.1996.542658.

[63]

L. Paquete and T. Stützle, An experimental investigation of iterated local search for coloring graphs,, in Applications of Evolutionary Computing (eds. S. Cagnoni, (2279), 122.

[64]

P. M. Pardalos and O. V. Shylo, An algorithm for the job shop scheduling problem based on global equilibrium search techniques,, Computational Management Science, 3 (2006), 331. doi: 10.1007/s10287-006-0023-y.

[65]

F. Pezzella, G. Morganti and G. Ciaschetti, A genetic algorithm for the flexible job-shop scheduling problem,, Computers and Operations Research, 35 (2008), 3202. doi: 10.1016/j.cor.2007.02.014.

[66]

S. Rahmati, M. Zandieh and M. Yazdani, Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem,, The International Journal of Advanced Manufacturing Technology, 64 (2013), 915. doi: 10.1007/s00170-012-4051-1.

[67]

M. Rajkumar, P. Asokan, N. Anilkumar and T. Page, A grasp algorithm for flexible job-shop scheduling problem with limited resource constraints,, International Journal of Production Research, 49 (2011), 2409. doi: 10.1080/00207541003709544.

[68]

M. Rohaninejad, A. Kheirkhah, P. Fattahi and B. Vahedi-Nouri, A hybrid multi-objective genetic algorithm based on the electre method for a capacitated flexible job shop scheduling problem,, The International Journal of Advanced Manufacturing Technology, 77 (2015), 51. doi: 10.1007/s00170-014-6415-1.

[69]

V. Roshanaei, A. Azab and H. ElMaraghy, Mathematical modelling and a meta-heuristic for flexible job shop scheduling,, International Journal of Production Research, 51 (2013), 6247. doi: 10.1080/00207543.2013.827806.

[70]

C. R. Schrich, V. A. Armentano and M. Laguna, Tardiness minimization in a flexible job shop: A tabu search approach,, Journal of Intelligent Manufacturing, 15 (2004), 103.

[71]

X. Shao, W. Liu, Q. Liu and C. Zhang, Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem,, The International Journal of Advanced Manufacturing Technology, 67 (2013), 2885. doi: 10.1007/s00170-012-4701-3.

[72]

T. Stützle, Iterated local search for the quadratic assignment problem,, European Journal of Operational Research, 174 (2006), 1519. doi: 10.1016/j.ejor.2005.01.066.

[73]

L. Tang and X. Wang, Iterated local search algorithm based on very large-scale neighborhood for prize-collecting vehicle routing problem,, The International Journal of Advanced Manufacturing Technology, 29 (2006), 1246. doi: 10.1007/s00170-005-0014-0.

[74]

J. C. Tay and N. B. Ho, Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems,, Computers and Industrial Engineering, 54 (2008), 453. doi: 10.1016/j.cie.2007.08.008.

[75]

S. J. Wang, B. H. Zhou and L. F. Xi, A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem,, International Journal of Production Research, 46 (2008), 3027.

[76]

X. J. Wang, L. Gao, C. Y. Zhang and X. Y. Shao, A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem,, International Journal of Advanced Manufacturing Technology, 51 (2010), 757. doi: 10.1007/s00170-010-2642-2.

[77]

Y. Wang, H. Yin and K. Qin, A novel genetic algorithm for flexible job shop scheduling problems with machine disruptions,, The International Journal of Advanced Manufacturing Technology, 68 (2013), 1317. doi: 10.1007/s00170-013-4923-z.

[78]

W. J. Xia and Z. M. Wu, An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems,, Computers and Industrial Engineering, 48 (2005), 409. doi: 10.1016/j.cie.2005.01.018.

[79]

L. N. Xing, Y. W. Chen and K. W. Yang, Multi-population interactive coevolutionary algorithm for flexible job shop scheduling problems,, Computational Optimization and Applications, 48 (2011), 139. doi: 10.1007/s10589-009-9244-7.

[80]

M. Yazdani, M. Amiri and M. Zandieh, Flexible job-shop scheduling with parallel variable neighborhood search algorithm,, Expert Systems with Applications, 37 (2010), 678. doi: 10.1016/j.eswa.2009.06.007.

[81]

Y. Yuan and H. Xu, Flexible job shop scheduling using hybrid differential evolution algorithms,, Computers & Industrial Engineering, 65 (2013), 246. doi: 10.1016/j.cie.2013.02.022.

[82]

Y. Yuan and H. Xu, An integrated search heuristic for large-scale flexible job shop scheduling problems,, Computers & Operations Research, 40 (2013), 2864. doi: 10.1016/j.cor.2013.06.010.

[83]

Y. Yuan and H. Xu, Multiobjective flexible job shop scheduling using memetic algorithms,, Automation Science and Engineering, 12 (2015), 336. doi: 10.1109/TASE.2013.2274517.

[84]

Y. Yuan, H. Xu and J. Yang, A hybrid harmony search algorithm for the flexible job shop scheduling problem,, Applied Soft Computing, 13 (2013), 3259. doi: 10.1016/j.asoc.2013.02.013.

[85]

G. H. Zhang, X. Y. Shao, P. G. Li and L. Gao, An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem,, Computers and Industrial Engineering, 56 (2009), 1309. doi: 10.1016/j.cie.2008.07.021.

[86]

Q. Zhang and J. Sun, Iterated local search with guided mutation,, 2006 IEEE International Conference on Evolutionary Computation, (): 924.

[87]

M. Ziaee, A heuristic algorithm for solving flexible job shop scheduling problem,, The International Journal of Advanced Manufacturing Technology, 71 (2014), 519. doi: 10.1007/s00170-013-5510-z.

[88]

N. Zribi, I. Kacem, A. El Kamel and P. Borne, Assignment and scheduling in flexible job-shops by hierarchical optimization,, Ieee Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 37 (2007), 652. doi: 10.1109/TSMCC.2007.897494.

[1]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[2]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253

[3]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[4]

Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95

[5]

Lassi Roininen, Markku S. Lehtinen. Perfect pulse-compression coding via ARMA algorithms and unimodular transfer functions. Inverse Problems & Imaging, 2013, 7 (2) : 649-661. doi: 10.3934/ipi.2013.7.649

[6]

Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191

[7]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637

[8]

Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87

[9]

Miguel Mendes. A note on the coding of orbits in certain discontinuous maps. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 369-382. doi: 10.3934/dcds.2010.27.369

[10]

Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577

[11]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[12]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041

[13]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[14]

Carla Mascia, Giancarlo Rinaldo, Massimiliano Sala. Hilbert quasi-polynomial for order domains and application to coding theory. Advances in Mathematics of Communications, 2018, 12 (2) : 287-301. doi: 10.3934/amc.2018018

[15]

T. Jäger. Neuronal coding of pacemaker neurons -- A random dynamical systems approach. Communications on Pure & Applied Analysis, 2011, 10 (3) : 995-1009. doi: 10.3934/cpaa.2011.10.995

[16]

Shinsuke Koyama, Lubomir Kostal. The effect of interspike interval statistics on the information gain under the rate coding hypothesis. Mathematical Biosciences & Engineering, 2014, 11 (1) : 63-80. doi: 10.3934/mbe.2014.11.63

[17]

Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145

[18]

Pengyu Yan, Shi Qiang Liu, Cheng-Hu Yang, Mahmoud Masoud. A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking. Journal of Industrial & Management Optimization, 2019, 15 (1) : 221-233. doi: 10.3934/jimo.2018040

[19]

Jie Huang, Marco Donatelli, Raymond H. Chan. Nonstationary iterated thresholding algorithms for image deblurring. Inverse Problems & Imaging, 2013, 7 (3) : 717-736. doi: 10.3934/ipi.2013.7.717

[20]

Chi Zhou, Wansheng Tang, Ruiqing Zhao. Optimal consumption with reference-dependent preferences in on-the-job search and savings. Journal of Industrial & Management Optimization, 2017, 13 (1) : 505-529. doi: 10.3934/jimo.2016029

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (31)
  • HTML views (0)
  • Cited by (1)

[Back to Top]