The aim of the paper is to present a new approach based on the Cellular Automata technique for a specific class of scheduling problems with parallel machines (in which some important parameter values cannot be determined a priori). The problem domain is represented by an asynchronous non-homogeneous cellular automaton. In addition, the division of the method into three levels is introduced. Inseparable use of simulation, optimization and result levels, is proposed. To illustrate our proposition, the optimization problem of drilling tunnels in a given area is considered. A number of simulation experiments were performed involving different instances of the problem and the results are presented and discussed in the paper.
BandiniSCrocianiLGorriniAVizzariG.An agent-based model of pedestrian dynamics considering groups: A real world case study. 2014 IEEE 17th international conference on intelligent transportation systems (ITSC), October 2014, pp. 572–577.
2.
BattyM.Cities and Complexity: Understanding Cities with Cellular Automata, Agent-Based Models, and Fractals. Cambridge, MA: The MIT Press, 2007.
TopaPMlocekP.Using shared memory as a cache in cellular automata water flow simulations on GPUs. Comput Sci2013; 14: 385–401.
5.
WąsJLubaśR.Towards realistic and effective agent-based models of crowd dynamics. Neurocomputing2014; 146: 199–209.
6.
BruckerP.Scheduling algorithms, Volume 3. New York: Springer, 2007.
7.
GawiejnowiczS.Time-dependent scheduling. New York: Springer Publishing Company Incorporated, 2008.
8.
JarbouiBSiarryPTeghemJ.Metaheuristics for production scheduling. New York: Wiley Online Library, 2013.
9.
DraaAMeshoulS.A quantum inspired learning cellular automaton for solving the travelling salesman problem. In 2010 12th international conference on computer modelling and simulation (UKSim), March 2010, pp. 45–50.
10.
ŚwiecickaASeredyńskiF.Cellular automata approach to scheduling problem. In 2000 international conference on parallel computing in electrical engineering (PARELEC 2000), Quebec, Canada, 27–30 August 2000, pp. 29–33
11.
ŚwiecickaASeredyńskiFZomayaAY.Multiprocessor scheduling and rescheduling with use of cellular automata and artificial immune system support. IEEE Trans Parallel Distrib Syst2006; 17: 253–262.
12.
SeredyńskiFZomayaAY.Sequential and parallel cellular automata-based scheduling algorithms. IEEE Trans Parallel Distrib Syst2002; 13: 1009–1023.
13.
VidicaPMde OliveiraGMB. Cellular automata-based scheduling: A new approach to improve generalization ability of evolved rules. In IEEE ninth Brazilian symposium on neural networks, 2006 (SBRN’06), 2006, pp. 18–23.
14.
TretyakovaASeredynskiFBouvryP.Cellular automata approach to maximum lifetime coverage problem in wireless sensor networks. In Cellular Automata - 11th international conference on cellular automata for research and industry (ACRI 2014), Krakow, Poland, 22–25 September 2014, pp. 437–446.
15.
AbdolzadehMRashidiH.An approach of cellular learning automata to job shop scheduling problem. Int J Sim Syst Sci Technol2010; 34: 391–401.
16.
AntczakAAntczakPWitkowskiT.Using of evolving cellular automata for flexible job shop with makespan criterion. In IEEE international workshop on intelligent data acquisition and advanced computing systems: technology and applications, 2009 (IDAACS 2009), September 2009, pp. 297–302.
17.
ShimuraKNishinariK.Project management and critical path analysis: a cellular automaton model. J Cellular Automata2014; 9: 257–270.
18.
MalarzKKowalska-StyczeńAKułakowskiK.Impact of the workers’ loyalty on the group performance modeled by a bi-layer cellular automaton with a hysteretic rule. ArXiv e-prints, November2014.
19.
Dudek-DyduchE.Learning based algorithm in scheduling. J Intell Manuf2000; 11: 135–143.
20.
Dudek-DyduchEDutkiewiczL. Substitution tasks method for discrete optimization. In Proceedings of the 12th international conference artificial intelligence and soft computing (ICAISC 2013), Zakopane, Poland, 9–13 June 2013, Part II, pp. 419–430.
21.
Dudek-DyduchEKucharskaE. Learning method for co-operation. In Proceedings 3rd international conference on computational collective intelligence: technologies and applications (ICCCI 2011), Gdynia, Poland, 21–23 September 2011, Part II, pp. 290–300.
22.
Dudek-DyduchEKucharskaEDutkiewiczLRączkaK. ALMM solver - A tool for optimization problems. In: Proceedings of the 13th international conference artificial intelligence and soft computing (ICAISC 2014), Zakopane, Poland, 1–5 June 2014, Part II, pp. 328–338.
23.
KucharskaEDutkiewiczLRączkaKGrobler-DębskaK.ALMM approach for optimization of the supply routes for multi-location companies problem. In KICSS 2013: looking into the future of creativity and decision support systems: proceedings of the 8th international conference on knowledge, information and creativity support systems, Krakow, Poland, 7–9 November 2013 ( Advances in Decision Sciences and Future Studies, vol. 2), 2013, pp. 321–332.
24.
SadeghiSAriafarSGhanbariMIsmailN.An optimization approach to solve a multi-objective unrelated parallel machine scheduling problem. Appl Mech Mater2014; 564: 585–589.
25.
ChangPCChenSHLinKL.Two-phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Syst Appl2005; 29: 705–712.
26.
DutkiewiczLKucharskaEKraszewskaM.Scheduling of preparatory work in mine - Simulation algorithms. Gospodarka Surowcami Mineralnymi2008; 24(3): 79–93.
27.
Yun-ChiaLYu-MingHChia-YunT.Metaheuristics for drilling operation scheduling in Taiwan {PCB} industries. Int J Production Econ2013; 141: 189–198.
28.
YuLShihHMPfundMCarlyleWMFowlerJW.Scheduling of unrelated parallel machines: an application to PWB manufacturing. IIE Trans2002; 34: 921–931.
29.
LiSLiuYLandersRG.An adaptive evolutionary algorithm for optimizing process planning of parallel drilling operations. Int J Adv Manuf Technol2015; 79: 1247–1263.
30.
BłażewiczJ.Computational complexity in the computer systems design. Poznan: Publishing House of Poznan University of Technology, 1984.
31.
GrahamRLLawlerELLenstraJKRinnooy KanAHG. Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math1979; 5: 287–326.
