research-article

ACO with automatic parameter selection for a scheduling problem with a group cumulative constraint

Authors:

Samba N. Ndiaye,

Christine SolnonAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Pages 13 - 21

https://doi.org/10.1145/3377930.3389818

Published: 26 June 2020 Publication History

Abstract

We consider a RCPSP (resource constrained project scheduling problem), the goal of which is to schedule jobs on machines in order to minimise job tardiness. This problem comes from a real industrial application, and it requires an additional constraint which is a generalisation of the classical cumulative constraint: jobs are partitioned into groups, and the number of active groups must never exceeds a given capacity (where a group is active when some of its jobs have started while some others are not yet completed). We first study the complexity of this new constraint. Then, we describe an Ant Colony Optimisation algorithm to solve our problem, and we compare three different pheromone structures for it. We study the influence of parameters on the solving process, and show that it varies from an instance to another. Hence, we identify a subset of parameter settings with complementary strengths and weaknesses, and we use a per-instance algorithm selector in order to select the best setting for each new instance to solve. We experimentally compare our approach with a tabu search approach and an exact approach on a data set coming from our industrial application.

References

[1]

Abderrahmane Aggoun and Nicolas Beldiceanu. 1993. Extending chip in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling 17, 7 (April 1993), 57--73.

Digital Library

[2]

Philippe Baptiste and Nicolas Bonifas. 2018. Redundant cumulative constraints to compute preemptive bounds. Discrete Applied Mathematics 234 (Jan. 2018), 168--177.

[3]

Nicolas Bonifas. 2016. A O(n2 log(n)) propagation for the Energy Reasoning. (2016), 4.

[4]

Peter Brucker, Andreas Drexl, Rolf Möhring, Klaus Neumann, and Erwin Pesch. 1999. Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112, 1 (Jan. 1999), 3--41.

[5]

Alberto Colorni, Marco Dorigo, and Vittorio Maniezzo. 1991. Distributed Optimization by Ant Colonies. In Proceedings of the First European Conference on Artificial Life.

[6]

Marco Dorigo and Thomas Stützle. 2004. Ant colony optimization. MIT Press, Cambridge, Mass. OCLC: 834298732.

[7]

Fred Glover, James P. Kelly, and Manuel Laguna. 1996. New advances and applications of combining simulation and optimization. In Proceedings of the 28th conference on Winter simulation - WSC '96. ACM Press, Coronado, California, United States, 144--152.

Digital Library

[8]

Michael Guntsch and Martin Middendorf. 2002. Applying Population Based ACO to Dynamic Optimization Problems. In Ant Algorithms (Lecture Notes in Computer Science). Springer, Berlin, Heidelberg, 111--122.

[9]

Sönke Hartmann and Rainer Kolisch. 2000. Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research 127, 2 (Dec. 2000), 394--407.

[10]

F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stuetzle. 2009. ParamILS: An Automatic Algorithm Configuration Framework. Journal of Artificial Intelligence Research 36 (Oct. 2009), 267--306.

[11]

Madjid Khichane, Patrick Albert, and Christine Solnon. 2009. An ACO-Based Reactive Framework for Ant Colony Optimization: First Experiments on Constraint Satisfaction Problems. In Learning and Intelligent Optimization. Vol. 5851. Springer Berlin Heidelberg, Berlin, Heidelberg, 119--133.

Digital Library

[12]

Lars Kotthoff. 2014. Algorithm Selection for Combinatorial Search Problems: A Survey. AI Magazine 35, 3 (Sept. 2014), 48--60.

[13]

Lars Kotthoff. 2014. LLAMA: Leveraging Learning to Automatically Manage Algorithms. arXiv:1306.1031 [cs] (April 2014). http://arxiv.org/abs/1306.1031 arXiv: 1306.1031.

[14]

Kuan Yew Wong and Komarudin. 2008. Parameter tuning for ant colony optimization: A review. In 2008 International Conference on Computer and Communication Engineering. IEEE, Kuala Lumpur, Malaysia, 542--545.

[15]

Philippe Laborie, Jérôme Rogerie, Paul Shaw, and Petr Vilím. 2018. IBM ILOG CP optimizer for scheduling: 20+ years of scheduling with constraints at IBM/ILOG. Constraints 23, 2 (April 2018), 210--250.

Digital Library

[16]

Jae-Ho Lee, Jae-Min Yu, and Dong-Ho Lee. 2013. A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness. The International Journal of Advanced Manufacturing Technology 69, 9-12 (Dec. 2013), 2081--2089.

[17]

Young Hoon Lee and Michael Pinedo. 1997. Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research 100, 3 (Aug. 1997), 464--474.

[18]

Pengpeng Lin, Jun Zhang, and Marco A. Contreras. 2015. Automatically configuring ACO using multilevel ParamILS to solve transportation planning problems with underlying weighted networks. Swarm and Evolutionary Computation 20 (Feb. 2015), 48--57.

[19]

Manuel López-Ibáñez and Thomas Stützle. 2010. Automatic Configuration of Multi-Objective ACO Algorithms. In Swarm Intelligence. Vol. 6234. Springer Berlin Heidelberg, Berlin, Heidelberg, 95--106.

[20]

D. Merkle, M. Middendorf, and H. Schmeck. 2002. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation 6, 4 (Aug. 2002), 333--346.

Digital Library

[21]

Klaus Neumann and Christoph Schwindt. 2003. Project scheduling with inventory constraints. Mathematical Methods of Operations Research (ZOR) 56, 3 (Jan. 2003), 513--533.

[22]

Héctor Neyoy, Oscar Castillo, and José Soria. 2013. Dynamic Fuzzy Logic Parameter Tuning for ACO and Its Application in TSP Problems. In Recent Advances on Hybrid Intelligent Systems. Vol. 451. Springer Berlin Heidelberg, Berlin, Heidelberg, 259--271.

[23]

Pierre Ouellet and Claude-Guy Quimper. 2013. Time-Table Extended-Edge-Finding for the Cumulative Constraint. In Principles and Practice of Constraint Programming. Vol. 8124. Springer Berlin Heidelberg, Berlin, Heidelberg, 562--577.

[24]

Michael L. Pinedo. 2016. Scheduling. Springer International Publishing, Cham.

[25]

Mauricio G. C. Resende and Celso C. Ribeiro. 2003. Greedy Randomized Adaptive Search Procedures. In Handbook of Metaheuristics. Springer US, Boston, MA, 219--249.

[26]

J.M.J. Schutten. 1996. List scheduling revisited. Operations Research Letters 18, 4 (Feb. 1996), 167--170.

Digital Library

[27]

Krzysztof Socha and Marco Dorigo. 2008. Ant colony optimization for continuous domains. European Journal of Operational Research 185, 3 (March 2008), 1155--1173.

[28]

Wouter Souffriau, Pieter Vansteenwegen, Greet Vanden Berghe, and Dirk Van Oudheusden. 2008. Automated Parameterisation of a Metaheuristic for the Orienteering Problem. In Adaptive and Multilevel Metaheuristics. Vol. 136. Springer Berlin Heidelberg, Berlin, Heidelberg, 255--269.

[29]

T. Stützle and H. Hoos. 1998. Improvements on the Ant-System: Introducing the MAX-MIN Ant System. In Artificial Neural Nets and Genetic Algorithms. Springer Vienna, Vienna, 245--249.

[30]

R.F. Tavares Neto and M. Godinho Filho. 2013. Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research. Engineering Applications of Artificial Intelligence 26, 1 (Jan. 2013), 150--161.

Digital Library

[31]

L. Xu, F. Hutter, H. H. Hoos, and K. Leyton-Brown. 2008. SATzilla: Portfolio-based Algorithm Selection for SAT. Journal of Artificial Intelligence Research 32 (July 2008), 565--606.

Cited By

Baroud MEghtesad AAhmed Mahdi MBahojb Nouri MWorya Khordehbinan MLee S(2023)A New Method for Solving the Flow Shop Scheduling Problem on Symmetric Networks Using a Hybrid Nature-Inspired AlgorithmSymmetry10.3390/sym1507140915:7(1409)Online publication date: 13-Jul-2023
https://doi.org/10.3390/sym15071409
Sibaroni YPrasetiyowati SFairuz MDamar MSalis R(2022)Performance Analysis of ACO and FA Algorithms on Parameter Variation Scenarios in Determining Alternative Routes for Cars as a Solution to Traffic JamsJurnal Online Informatika10.15575/join.v7i1.7977:1(97-109)Online publication date: 30-Jun-2022
https://doi.org/10.15575/join.v7i1.797
Ferreira ASoares ÂSantos ABastos JVarela L(2022)Analysis and Comparison of DABC and ACO in a Scheduling ProblemInnovations in Mechatronics Engineering II10.1007/978-3-031-09385-2_19(203-215)Online publication date: 21-Jun-2022
https://doi.org/10.1007/978-3-031-09385-2_19
Show More Cited By

Index Terms

ACO with automatic parameter selection for a scheduling problem with a group cumulative constraint
1. Applied computing
  1. Operations research
    1. Industry and manufacturing
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness
  2. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Scheduling Cellular Manufacturing Systems Using ACO and GA

In this paper, cellular manufacturing scheduling problems are studied. The objective is to minimize makespan (Cmax) considering part family in the manufacturing cell flow line where the setup times are sequence dependent. Minimizing Cmax will result in ...
Solving the Group Cumulative Scheduling Problem with CPO and ACO
Principles and Practice of Constraint Programming
Abstract
The Group Cumulative Scheduling Problem (GCSP) comes from a real application, i.e., order preparation in food industry. Each order is composed of jobs which must be scheduled on machines, and the goal is to minimize the sum of job tardiness. There ...
Minimizing total completion time in two-machine flow shops with exact delay using genetic algorithm & ant colony algorithm
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

We study the problem of minimizing total completion time in a two-machine flow shop with exact delay. There are n jobs, one upstream machine M1 and one downstream machine M2. Each job has to be processed first on machine M1, then on machine M2, and has ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

June 2020

1349 pages

ISBN:9781450371285

DOI:10.1145/3377930

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Copyright © 2020 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
74
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Baroud MEghtesad AAhmed Mahdi MBahojb Nouri MWorya Khordehbinan MLee S(2023)A New Method for Solving the Flow Shop Scheduling Problem on Symmetric Networks Using a Hybrid Nature-Inspired AlgorithmSymmetry10.3390/sym1507140915:7(1409)Online publication date: 13-Jul-2023
https://doi.org/10.3390/sym15071409
Sibaroni YPrasetiyowati SFairuz MDamar MSalis R(2022)Performance Analysis of ACO and FA Algorithms on Parameter Variation Scenarios in Determining Alternative Routes for Cars as a Solution to Traffic JamsJurnal Online Informatika10.15575/join.v7i1.7977:1(97-109)Online publication date: 30-Jun-2022
https://doi.org/10.15575/join.v7i1.797
Ferreira ASoares ÂSantos ABastos JVarela L(2022)Analysis and Comparison of DABC and ACO in a Scheduling ProblemInnovations in Mechatronics Engineering II10.1007/978-3-031-09385-2_19(203-215)Online publication date: 21-Jun-2022
https://doi.org/10.1007/978-3-031-09385-2_19
Groleaz LNdiaye SSolnon C(2020)Solving the Group Cumulative Scheduling Problem with CPO and ACOPrinciples and Practice of Constraint Programming10.1007/978-3-030-58475-7_36(620-636)Online publication date: 2-Sep-2020
https://doi.org/10.1007/978-3-030-58475-7_36

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents