{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T08:54:29Z","timestamp":1768985669407,"version":"3.49.0"},"reference-count":28,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T00:00:00Z","timestamp":1669680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Machine scheduling is a hard combinatorial problem having many manifestations in real life. Due to the schedule followed, the possibility of installations of machines operating sub-optimally is high. In this work, we examine the problem of a single machine with time-dependent capacity that performs jobs of deterministic durations, while for each job, its due time is known in advance. The objective is to minimize the aggregated tardiness in all tasks. The problem was motivated by the need to schedule charging times of electric vehicles effectively. We formulate an integer programming model that clearly describes the problem and a constraint programming model capable of effectively solving it. Due to the usage of interval variables, global constraints, a powerful constraint programming solver, and a heuristic we have identified, which we call the \u201cdue times rule\u201d, the constraint programming model can reach excellent solutions. Furthermore, we employ a hybrid approach that exploits three local search improvement procedures in a schema where the constraint programming part of the solver plays a central role. These improvement procedures exhaustively enumerate portions of the search space by exchanging consecutive jobs with a single job of the same duration, moving cost-incurring jobs to earlier times in a consecutive sequence of jobs or even exploiting periods where capacity is not fully utilized to rearrange jobs. On the other hand, subproblems are given to the exact constraint programming solver, allowing freedom of movement only to certain parts of the schedule, either in vertical ribbons of the time axis or in groups of consecutive sequences of jobs. Experiments on publicly available data show that our approach is highly competitive and achieves the new best results in many problem instances.<\/jats:p>","DOI":"10.3390\/a15120450","type":"journal-article","created":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T02:09:58Z","timestamp":1669687798000},"page":"450","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Hybrid Exact\u2013Local Search Approach for One-Machine Scheduling with Time-Dependent Capacity"],"prefix":"10.3390","volume":"15","author":[{"given":"Christos","family":"Valouxis","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Patras, 26500 Patras, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1113-8462","authenticated-orcid":false,"given":"Christos","family":"Gogos","sequence":"additional","affiliation":[{"name":"Department of Informatics and Telecommunications, University of Ioannina, 47100 Arta, Greece"}]},{"given":"Angelos","family":"Dimitsas","sequence":"additional","affiliation":[{"name":"Department of Informatics and Telecommunications, University of Ioannina, 47100 Arta, Greece"}]},{"given":"Petros","family":"Potikas","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, National Technical University of Athens, 15772 Athens, Greece"}]},{"given":"Anastasios","family":"Vittas","sequence":"additional","affiliation":[{"name":"Department of Informatics and Telecommunications, University of Ioannina, 47100 Arta, Greece"}]}],"member":"1968","published-online":{"date-parts":[[2022,11,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Pinedo, M.L. (2012). Scheduling, Springer.","DOI":"10.1007\/978-1-4614-2361-4"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"Volume 5","author":"Graham","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"ref_3","unstructured":"(2022, November 21). Scheduling Zoo. Available online: http:\/\/schedulingzoo.lip6.fr\/."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Menc\u00eda, C., Sierra, M.R., Menc\u00eda, R., and Varela, R. (2017, January 19\u201323). Genetic algorithm for scheduling charging times of electric vehicles subject to time dependent power availability. Proceedings of the International Work-Conference on the Interplay between Natural and Artificial Computation, Corunna, Spain.","DOI":"10.1007\/978-3-319-59740-9_16"},{"key":"ref_5","first-page":"49","article-title":"Evolutionary one-machine scheduling in the context of electric vehicles charging","volume":"26","author":"Sierra","year":"2019","journal-title":"Integr.-Comput.-Aided Eng."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Menc\u00eda, R., and Menc\u00eda, C. (2021). One-Machine Scheduling with Time-Dependent Capacity via Efficient Memetic Algorithms. Mathematics, 9.","DOI":"10.3390\/math9233030"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2009.04.007","article-title":"The single-machine total tardiness scheduling problem: Review and extensions","volume":"202","author":"Koulamas","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_8","unstructured":"(2022, November 21). GitHub Repository for \u201cOne Machine Scheduling with Time Dependent Capacity via Efficient Memetic Algorithms\u201d by Mencia R. Available online: https:\/\/github.com\/raulmencia\/One-Machine-Scheduling-with-Time-Dependent-Capacity-via-Efficient-Memetic-Algorithms."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.cie.2015.04.002","article-title":"Electric vehicle charging under power and balance constraints as dynamic scheduling","volume":"85","author":"Puente","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","article-title":"Complexity of machine scheduling problems","volume":"Volume 1","author":"Lenstra","year":"1977","journal-title":"Annals of Discrete Mathematics"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0305-0483(87)90071-5","article-title":"Single machine scheduling research","volume":"15","author":"Gupta","year":"1987","journal-title":"Omega"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.future.2016.01.016","article-title":"Scheduling independent tasks on heterogeneous processors using heuristics and Column Pricing","volume":"60","author":"Gogos","year":"2016","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Baptiste, P., Le Pape, C., and Nuijten, W. (2001). Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems, Springer Science & Business Media.","DOI":"10.1007\/978-1-4615-1479-4"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Gro\u00dfmann, P., H\u00f6lldobler, S., Manthey, N., Nachtigall, K., Opitz, J., and Steinke, P. (2012, January 9\u201312). Solving periodic event scheduling problems with SAT. Proceedings of the International Conference on Industrial, Engineering and other Applications of Applied Intelligent Systems, Dalian, China.","DOI":"10.1007\/978-3-642-31087-4_18"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ans\u00f3tegui, C., Bofill, M., Palah\u00ed, M., Suy, J., and Villaret, M. (2011, January 17\u201318). Satisfiability modulo theories: An efficient approach for the resource-constrained project scheduling problem. Proceedings of the Ninth Symposium of Abstraction, Reformulation, and Approximation, Parador de Cardona, Spain.","DOI":"10.1007\/s10601-012-9131-1"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0377-2217(97)00335-4","article-title":"A branch and bound algorithm for the resource-constrained project scheduling problem","volume":"107","author":"Brucker","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1287\/ijoc.8.3.302","article-title":"Job shop scheduling by local search","volume":"8","author":"Vaessens","year":"1996","journal-title":"Informs J. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/BF02022094","article-title":"A controlled search simulated annealing method for the single machine weighted tardiness problem","volume":"21","author":"Matsuo","year":"1989","journal-title":"Ann. Oper. Res."},{"key":"ref_19","first-page":"60","article-title":"A genetic algorithm for general machine scheduling problems","volume":"Volume 2","author":"Lee","year":"1998","journal-title":"Proceedings of the 1998 Second International Conference Knowledge-Based Intelligent Electronic Systems, Proceedings KES\u201998 (Cat. No. 98EX111)"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"105782","DOI":"10.1016\/j.asoc.2019.105782","article-title":"Evolving priority rules for on-line scheduling of jobs on a single machine with variable capacity over time","volume":"85","author":"Sierra","year":"2019","journal-title":"Appl. Soft Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/S0377-2217(00)00140-5","article-title":"A memetic algorithm for the total tardiness single machine scheduling problem","volume":"132","author":"Mendes","year":"2001","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.omega.2018.01.001","article-title":"A memetic differential evolution algorithm for energy-efficient parallel machine scheduling","volume":"82","author":"Wu","year":"2019","journal-title":"Omega"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1023\/A:1020999407672","article-title":"Ant colony optimization with global pheromone evaluation for scheduling a single machine","volume":"18","author":"Merkle","year":"2003","journal-title":"Appl. Intell."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2629","DOI":"10.1016\/j.eswa.2009.08.015","article-title":"An efficient job-shop scheduling algorithm based on particle swarm optimization","volume":"37","author":"Lin","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1016\/j.cie.2017.07.018","article-title":"Hybrid Genetic Bees Algorithm applied to single machine scheduling with earliness and tardiness penalties","volume":"113","author":"Yuce","year":"2017","journal-title":"Comput. Ind. Eng."},{"key":"ref_26","unstructured":"(2022, November 21). GitHub Repository for \u201cA Hybrid Exact-Local Search Approach for One-Machine Scheduling with Time-Dependent Capacity\u201d by Gogos C. Available online: https:\/\/github.com\/chgogos\/1MSTDC."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/s10601-018-9281-x","article-title":"IBM ILOG CP optimizer for scheduling","volume":"23","author":"Laborie","year":"2018","journal-title":"Constraints"},{"key":"ref_28","unstructured":"(2022, November 21). Google OR Tools CP-SAT Solver. Available online: https:\/\/developers.google.com\/optimization\/cp\/cp_solver."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/12\/450\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:28:57Z","timestamp":1760146137000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/12\/450"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,29]]},"references-count":28,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["a15120450"],"URL":"https:\/\/doi.org\/10.3390\/a15120450","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,29]]}}}