This paper studies the computation of ensembles of priority rules for the One Machine Scheduling Problem with variable capacity and total tardiness minimization. Concretely, we address the problem of building optimal ensembles of priority rules, starting from a pool of rules evolved by a Genetic Programming approach. Building on earlier work, we propose a number of new algorithms. These include an iterated greedy search method, a local search algorithm and a memetic algorithm. Experimental results show the potential of the proposed approaches.
GrahamRLLawlerELLenstraJKKanAHGR. Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Annals of Discrete Mathematics. 1979; 5: 287-326.
2.
Hernández-ArauzoAPuenteJVarelaRSedanoJ. Electric vehicle charging under power and balance constraints as dynamic scheduling. Computers & Industrial Engineering. 2015; 85: 306-315.
3.
KoulamasC. The total tardiness problem: Review and extensions. Operations Research. 1994; 42: 1025-1041.
4.
PedrinoECRodaVOKatoERRSaitoJHTroncoMLTsunakiRH, et al. A Genetic Programming Based System for the Automatic Construction of Image Filters. Integr Comput-Aided Eng. 2013 Jul; 20(3): 275-287.
5.
ParisPCDPedrinoECNicolettiMC. Automatic learning of image filters using cartesian genetic programming. Integr Comput-Aided Eng. 2015 Apr; 22(2): 135-151.
6.
LunaJMRomeroJRRomeroCVenturaS. Reducing gaps in quantitative association rules: A genetic programming free-parameter algorithm. Integr Comput-Aided Eng. 2014 Oct; 21(4): 321-337.
7.
KozaJR. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.
8.
ParkJNguyenSZhangMJohnstonM. Evolving ensembles of dispatching rules using genetic programming for job shop scheduling. In: MachadoPHeywoodMIMcDermottJCastelliMGarcía-SánchezPBurelliP, et al., editors. Genetic Programming. Cham: Springer International Publishing. Proceedings of EuroGP 2015. Lecture Notes in ComputerScience. 2015; 9025: 92-104.
9.
HartESimK. A hyper-heuristic ensemble method for static job-shop scheduling. Evolutionary Computation. 2016; 24(4): 609-635.
10.
IngimundardottirHRunarssonTP. Discovering dispatching rules from data using imitation learning: A case study for the job-shop problem. Journal of Scheduling. 2018; 21(4): 413-428.
11.
DimopoulosCZalzalaAMS. Investigating the use of genetic programming for a classic one-machine scheduling problem. Advances in Engineering Software. 2001; 32(6): 489-498.
12.
Gil-GalaFJMencíaCSierraMRVarelaR. Evolving priority rules for on-line scheduling of jobs on a single machine with variable capacity over time. Applied Soft Computing. 2019; 85: 105782.
13.
DurasevićMJakobovićDKneževićK. Adaptive scheduling on unrelated machines with genetic programming. Applied Soft Computing. 2016; 48: 419-430.
14.
ChandSHuynhQSinghHRayTWagnerM. On the use of genetic programming to evolve priority rules for resource constrained project scheduling problems. Information Sciences. 2018; 432: 146-163.
15.
DumićMŠišejkovicDČorićRJakobovićD. Evolving priority rules for resource constrained project scheduling problem with genetic programming. Future Generation Computer Systems. 2018; 86: 211-221.
16.
MillerJFSmithSL. Redundancy and computational efficiency in Cartesian genetic programming. IEEE Transactions on Evolutionary Computation. 2006; 10(2): 167-174.
17.
ManazirARazaK. Recent developments in cartesian genetic programming and its variants. ACM Comput Surv. 2019; 51(6): 122:1-122:29.
18.
SimKHartE. Generating single and multiple cooperative heuristics for the one dimensional bin packing problem using a single node genetic programming island model. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. GECCO ’13. New York, NY, USA: ACM; 2013. pp. 1549-1556.
19.
NguyenSMeiYXueBZhangM. A Hybrid genetic programming algorithm for automated design of dispatching rules. Evolutionary Computation. 2019; 27(3): 467-496.
20.
BurkeEKHydeMRKendallGOchoaGÖzcanEWoodwardJR. In: GendreauMPotvinJY, editors. A classification of hyper-heuristic approaches: Revisited. Cham: Springer International Publishing. International Series in Operations Research & Management Science. 2019; 272: 453-477.
21.
LiXOlafssonS. Discovering dispatching rules using data mining. Journal of Scheduling. 2005 Dec; 8(6): 515-527.
22.
OlmoJLLunaJMRomeroJRVenturaS. Mining association rules with single and multi-objective grammar guided ant programming. Integr Comput-Aided Eng. 2013 Jul; 20(3): 217-234.
23.
Martínez-BallesterosMBacarditJTroncosoARiquelmeJC. Enhancing the scalability of a genetic algorithm to discover quantitative association rules in large-scale datasets. Integr Comput-Aided Eng. 2015 Jan; 22(1): 21-39.
24.
SunJLiHAdeliH. Concept drift oriented adaptive and dynamic support vector machine ensemble with time window in corporate financial risk prediction. IEEE Transactions on Systems, Man, and Cybernetics: Part A: Systems and Human. 2013 Jul; 43(4): 801-813.
25.
ParkJMeiYNguyenSChenGZhangM. An investigation of ensemble combination schemes for genetic programming based hyper-heuristic approaches to dynamic job shop scheduling. Applied Soft Computing. 2018; 63: 72-86.
26.
PolikarR. Ensemble based systems in decision making. IEEE Circuits and Systems Magazine. 2006; 6(3): 21-45.
27.
DurasevićMJakobovićD. Comparison of ensemble learning methods for creating ensembles of dispatching rules for the unrelated machines environment. Genetic Programming and Evolvable Machines. 2018 Jun; 19(1): 53-92.
28.
IbaH. Bagging, Boosting, and Bloating in Genetic Programming. In: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation – Volume 2. GECCO’99. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1999. pp. 1053-1060.
29.
ParisGRobilliardDFonluptC. Applying Boosting Techniques to Genetic Programming. In: ColletPFonluptCHaoJKLuttonESchoenauerM, editors. Artificial Evolution. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 267-278.
30.
DurasevićMJakobovićD. Creating dispatching rules by simple ensemble combination. Journal of Heuristics. 2019 May; 25: 959-1013.
31.
Gil-GalaFJVarelaR. Genetic Algorithm to Evolve Ensembles of Rules for On-Line Scheduling on Single Machine with Variable Capacity. In: Ferrández VicenteJMÁlvarez-SánchezJRde la Paz LópezFToledo MoreoJAdeliH, editors. From Bioinspired Systems and Biomedical Applications to Machine Learning. Cham: Springer International Publishing. Proceedings of IWINAC 2019. Lecture Notes in Computer Science. 2019; 11487: 223-233.
32.
MencíaCSierraMRMencíaRVarelaR. Evolutionary one-machine scheduling in the context of electric vehicles charging. Integrated Computer-Aided Engineering. 2019; 26(1): 49-63.
33.
KaplanSRabadiG. Exact and heuristic algorithms for the aerial refueling parallel machine scheduling problem with due date-to-deadline window and ready times. Computers & Industrial Engineering. 2012; 62(1): 276-285.
34.
HochbaumDS. Approximation Algorithms for NP-hard Problems. Boston, MA, USA: PWS Publishing Co., 1997, pp. 94-143.
35.
HungSLAdeliH. A parallel genetic/neural network learning algorithm for MIMD shared memory machines. IEEE Transactions on Neural Networks. 1994 Nov; 5(6): 900-909.
36.
AdeliHChengNT. Augmented Lagrangian genetic algorithm for structural optimization. Journal of Aerospace Engineering. 1994 Jan; 7: 104-118.
37.
AdeliHHungSL. Machine Learning – Neural Networks, Genetic Algorithms, and Fuzzy Sets. John Wiley and Sons, 1995.
MencíaRSierraMRMencíaCVarelaR. Genetic algorithms for the scheduling problem with arbitrary precedence relations and skilled operators. Integrated Computer-Aided Engineering. 2016; 23(3): 269-285.
40.
WolpertDHMacreadyWG. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation. 1997; 1(1): 67-82.
41.
KononovaAVCorneDWWildePShneerVCaraffiniF. Structural bias in population-based algorithms. Information Sciences. 2015; 298: 468-490.
42.
RaidlGRPuchingerJBlumC. In: GendreauMPotvinJY, editors. Metaheuristic Hybrids. Cham: Springer International Publishing; 2019, pp. 385-417.
43.
MencíaRSierraMRMencíaCVarelaR. Memetic algorithms for the job shop scheduling problem with operators. Applied Soft Computing. 2015; 34: 94-105.
44.
VelaCRVarelaRGonzálezMA. Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times. Journal of Heuristics. 2010; 16(2): 139-165.
45.
ZhuZXiaoJLiJQWangFZhangQ. Global path planning of wheeled robots using multi-objective memetic algorithms. Integr Comput-Aided Eng. 2015 Jan; 22(4): 387-404.
46.
HartWEKrasnogorNSmithJE (eds.) In: Recent Advances in Memetic Algorithms, Studies in Fuzzines and Soft Computing, Springer, Berlin, Germany, 2004, pp. 185-207.
47.
NeriFCottaCMoscatoP. In: Handbook of Memetic Algorithms, Studies in Computational Intelligence, Springer, Vol. 379, 2012.
ChenXOngYLimMTanKC. A multi-facet survey on memetic computation. IEEE Transactions on Evolutionary Computation. 2011; 5(15): 591-607.
50.
NeriFCottaC. Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation. 2012; 2: 1-14.
51.
CaraffiniFNeriFPicinaliL. An analysis on separability for Memetic Computing automatic design. Information Sciences. 2014; 265: 1-22.
52.
CaraffiniFNeriFEpitropakisM. HyperSPAM: A study on hyper-heuristic coordination strategies in the continuous domain. Information Sciences. 2019; 477: 186-202.
53.
BalasECarreraMC. A dynamic subgradient-based branch-and-bound procedure for set covering. Oper Res. 1996 Dec; 44(6): 875-890.
