Conclusions and References

Table of Links

Abstract and 1. Introduction

2. Mixed integer and constraint programming models

   2.1 Mixed-integer linear programming model

   2.2 Constraint Programming model

3. Constructive Heuristics

4. Benchmark instances

5. Numerical experiments

   5.1 Experiments with the constructive heuristics

   5.2 Solving the proposed models with a commercial solver

6. Conclusions and References

6 Conclusions

In this work, we addressed the FJS scheduling problem with sequencing flexibility and positionbased learning effect. To the authors’ knowledge, this combination, with potential application in a wide range of real-world industrial environments, has never been addressed in the literature. As a first step towards its efficient and effective solution, we introduced a set of 110 instances that transform into 330 instances by varying the learning rate α ∈ {0.1, 0.2, 0.3}. By introducing MILP and CP models, an exact solver aided by constructive heuristics was able to provide 183 proven optimal solutions. Instances, their solutions, models and constructive heuristics are all available for download at https://github.com/kennedy94/FJS. We expect this benchmark test-set to guide the introduction and evaluation of new effective heuristic and metaheuristic approaches for the considered problem. In fact, this is the current line of research of the authors.

Conflict of interest statement: On behalf of all authors, the corresponding author states that there is no conflict of interest.

Data availability: The datasets generated during and/or analysed during the current study are available in the GitHub repository, https://github.com/kennedy94/FJS.

References

[1] R. Alvarez-Valdes, A. Fuertes, J. M. Tamarit, G. Gim´enez, and R. Ramos. A heuristic to schedule flexible job-shop in a glass factory. European Journal of Operational Research, 165(2):525–534, 2005.

[2] J. L. Andrade-Pineda, D. Canca, P. L. Gonzalez-R, and M. Calle. Scheduling a dualresource flexible job shop with makespan and due date-related criteria. Annals of Operations Research, 291(1):5–35, 2020.

[3] A. Azzouz, M. Ennigrou, and L. Ben Said. Scheduling problems under learning effects: classification and cartography. International Journal of Production Research, 56(4):1642– 1661, 2017.

[4] E. G. Birgin, P. Feofiloff, C. G. Fernandes, E. L. De Melo, M. T. I. Oshiro, and D. P. Ronconi. A MILP model for an extended version of the flexible job shop problem. Optimization Letters, 8(4):1417–1431, 2014.

[5] E. G. Birgin, J. E. Ferreira, and D. P. Ronconi. List scheduling and beam search methods for the flexible job shop scheduling problem with sequencing flexibility. European Journal of Operational Research, 247(2):421–440, 2015.

[6] D. Biskup. Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1):173–178, 1999.

[7] D. Biskup. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188(2):315–329, 2008.

[8] Z.-C. Cao, C.-R. Lin, and M.-C. Zhou. A knowledge-based cuckoo search algorithm to schedule a flexible job shop with sequencing flexibility. IEEE Transactions on Automation Science and Engineering, 18(1):56–69, 2021.

[9] T. C. E. Cheng and G. Wang. Single machine scheduling with learning effect considerations. Annals of Operations Research, 98(1/4):273–290, 2000.

[10] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, Cambridge, MA, USA, 4th edition, 2022.

[11] P. Y. Gan and K. S. Lee. Scheduling of flexible-sequenced process plans in a mould manufacturing shop. The International Journal of Advanced Manufacturing Technology, 20(3):214– 222, 2002.

[12] J. Gao, M. Gen, and L. Sun. Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of Intelligent Manufacturing, 17(4):493–507, 2006.

[13] M. R. Garey, D. S. Johnson, and R. Sethi. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2):117–129, 1976.

[14] J. N. D. Gupta and S. K. Gupta. Single facility scheduling with nonlinear processing times. Computers and Industrial Engineering, 14(4):387–393, 1988.

[15] A. Janiak, T. Krysiak, and R. Trela. Scheduling problems with learning and ageing effects: A survey. Decision Making in Manufacturing and Services, 5(1):19–36, 2011.

[16] G. A. Kasapidis, S. Dauzere-Pees, D. C. Paraskevopoulos, P. P. Repoussis, and C. D. Tarantilis. On the multiresource flexible job-shop scheduling problem with arbitrary precedence graphs. Production and Operations Management, 32(7):2322–2330, 2023.

[17] G. A. Kasapidis, D. C. Paraskevopoulos, P. P. Repoussis, and C. D. Tarantilis. Flexible job shop scheduling problems with arbitrary precedence graphs. Production and Operations Management, 30(11):4044–4068, 2021.

[18] Y. K. Kim, K. Park, and J. Ko. A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Computers and Operations Research, 30(8):1151– 1171, 2003.

[19] P. Laborie, J. Rogerie, P. Shaw, and P. Vil´ım. IBM ILOG CP optimizer for scheduling: 20+ years of scheduling with constraints at ibm/ilog. Constraints, 23(2):210–250, 2018.

[20] J. Y.-T. Leung, H. Li, and M. Pinedo. Order scheduling in an environment with dedicated resources in parallel. Journal of Scheduling, 8(5):355–386, 2005.

[21] W. T. Lunardi, E. G. Birgin, P. Laborie, D. P. Ronconi, and H. Voos. Mixed integer linear programming and constraint programming models for the online printing shop scheduling problem. Computers and Operations Research, 123:105020, 2020.

[22] W. T. Lunardi, E. G. Birgin, D. P. Ronconi, and H. Voos. Metaheuristics for the online printing shop scheduling problem. European Journal of Operational Research, 293(2):419– 441, 2021.

[23] G. Vilcot and J.-C. Billaut. A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem. European Journal of Operational Research, 190(2):398–411, 2008.

[24] A. Vital-Soto, A. Azab, and M. F. Baki. Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility. Journal of Manufacturing Systems, 54:74–93, 2020.

[25] H. M. Wagner. An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly, 6(2):131–140, 1959.

[26] J. M. Wilson. Alternative formulations of a flow-shop scheduling problem. Journal of the Operational Research Society, 40(4):395–399, 1989.

[27] L. Yu, C. Zhu, J. Shi, and W. Zhang. An extended flexible job shop scheduling model for flight deck scheduling with priority, parallel operations, and sequence flexibility. Scientific Programming, 2017:1–15, 2017.