{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T11:24:09Z","timestamp":1770117849315,"version":"3.49.0"},"reference-count":40,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2023,4,12]],"date-time":"2023-04-12T00:00:00Z","timestamp":1681257600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Zhejiang Province Natural Science Foundation of China","award":["LY18G010012"],"award-info":[{"award-number":["LY18G010012"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper considers the single-machine problem with job release times and flexible preventive maintenance activities to minimize total weighted tardiness, a complicated scheduling problem for which many algorithms have been proposed in the literature. However, the considered problems are rarely solved by genetic algorithms (GAs), even though it has successfully solved various complicated combinatorial optimization problems. For the problem, we propose a trajectory-based immigration strategy, where immigrant generation is based on the given information of solution extraction knowledge matrices. We embed the immigration strategy into the GA method to improve the population\u2019s diversification process. To examine the performance of the proposed GA method, two versions of GA methods (the GA without immigration and the GA method with random immigration) and a mixed integer programming (MIP) model are also developed. Comprehensive experiments demonstrate the effectiveness of the proposed GA method by comparing the MIP model with two versions of GA methods. Overall, the proposed GA method significantly outperforms the other GA methods regarding solution quality due to the trajectory-based immigration strategy.<\/jats:p>","DOI":"10.3390\/a16040207","type":"journal-article","created":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T01:35:00Z","timestamp":1681349700000},"page":"207","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Trajectory-Based Immigration Strategy Genetic Algorithm to Solve a Single-Machine Scheduling Problem with Job Release Times and Flexible Preventive Maintenance"],"prefix":"10.3390","volume":"16","author":[{"given":"Shenquan","family":"Huang","sequence":"first","affiliation":[{"name":"College of Mechanical and Electrical Engineering, Wenzhou University, Wenzhou 325035, China"}]},{"given":"Ya-Chih","family":"Tsai","sequence":"additional","affiliation":[{"name":"Department of Hotel Management, Vanung University, Taoyuan 32061, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0055-7450","authenticated-orcid":false,"given":"Fuh-Der","family":"Chou","sequence":"additional","affiliation":[{"name":"College of Mechanical and Electrical Engineering, Wenzhou University, Wenzhou 325035, China"}]}],"member":"1968","published-online":{"date-parts":[[2023,4,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2257","DOI":"10.1016\/j.cor.2010.03.017","article-title":"A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival","volume":"37","author":"Chiang","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1016\/j.cie.2008.03.005","article-title":"Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness","volume":"55","author":"Sbihi","year":"2008","journal-title":"Comput. Ind. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/j.apm.2009.04.014","article-title":"Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance","volume":"34","author":"Low","year":"2010","journal-title":"Appl. Math. Model."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1016\/j.ejor.2013.10.052","article-title":"A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints","volume":"235","author":"Detienne","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.cor.2016.11.008","article-title":"Minimizing the makespan on a single machine with flexible maintenances and jobs\u2019 release dates","volume":"80","author":"Cui","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.cie.2018.06.017","article-title":"A scatter simulated annealing algorithm for the bi-objective scheduling problem for the wet station of semiconductor manufacturing","volume":"123","author":"Pang","year":"2018","journal-title":"Comput. Ind. Eng."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0167-5060(08)70742-8","article-title":"A pseudo-polynomial algorithm for sequencing jobs to minimize total tardiness","volume":"1","author":"Lawler","year":"1977","journal-title":"Ann. Discrete Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.cie.2009.04.014","article-title":"A survey of scheduling with deterministic machine availability constraints","volume":"58","author":"Ma","year":"2010","journal-title":"Comput. Ind. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1057\/palgrave.jors.2600791","article-title":"Scheduling maintenance on a single machine","volume":"50","author":"Qi","year":"1999","journal-title":"J. Oper. Res. Soc."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1016\/j.cie.2016.11.009","article-title":"Minimizing total absolute deviation of job completion times on a single machine with cleaning activities","volume":"103","author":"Su","year":"2017","journal-title":"Comput. Ind. Eng."},{"key":"ref_11","first-page":"383","article-title":"Minimizing the number of tardy jobs on unrelated parallel machines with dirt consideration","volume":"35","author":"Su","year":"2018","journal-title":"J. Ind. Prod. Eng."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Campo, E.A., Cano, J.A., Gomez-Montoya, R., Rodriguez-Velasquez, E., and Cortes, P. (2022). Flexible job shop scheduling problem with fuzzy times and due-windows: Minimizing weighted tardiness and earliness using genetic algorithms. Algorithms, 15.","DOI":"10.3390\/a15100334"},{"key":"ref_13","first-page":"63","article-title":"Minimizing the makespan in a single machine scheduling problem with flexible maintenance","volume":"19","author":"Yang","year":"2002","journal-title":"J. Chin. Inst. Ind. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.cie.2014.11.002","article-title":"Single-machine scheduling with a variable maintenance activity","volume":"79","author":"Luo","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.ejor.2007.06.029","article-title":"Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan","volume":"190","author":"Chen","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1016\/j.omega.2010.01.003","article-title":"Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities","volume":"38","author":"Yang","year":"2010","journal-title":"Omega"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.ejor.2003.08.026","article-title":"An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints","volume":"161","author":"Sadfi","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1016\/j.cor.2010.09.003","article-title":"Minimizing total completion time on a single machine with a flexible maintenance activity","volume":"38","author":"Yang","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1753","DOI":"10.1080\/00207540701636348","article-title":"Single machine scheduling with preventive maintenance","volume":"47","author":"Batun","year":"2009","journal-title":"Int. J. Prod. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.cie.2016.05.037","article-title":"Exact algorithms for single-machine scheduling problems with a variable maintenance","volume":"98","author":"Ying","year":"2016","journal-title":"Comput. Ind. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/BF00121681","article-title":"Machine scheduling with an availability constraint","volume":"9","author":"Lee","year":"1996","journal-title":"J. Glob. Optim."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.ijpe.2007.01.013","article-title":"Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint","volume":"112","author":"Kacem","year":"2008","journal-title":"Int. J. Prod. Econ."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/j.cie.2007.08.005","article-title":"Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval","volume":"54","author":"Kacem","year":"2008","journal-title":"Comput. Ind. Eng."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1016\/j.cor.2006.04.010","article-title":"Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times","volume":"35","author":"Kacem","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.camwa.2008.11.008","article-title":"Scheduling a maintenance activity to minimize total weighted completion time","volume":"57","author":"Mosheiov","year":"2009","journal-title":"Compu. Math. Appl."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1002\/(SICI)1520-6750(199910)46:7<845::AID-NAV6>3.0.CO;2-#","article-title":"Scheduling maintenance and semiresumable jobs on a single machine","volume":"46","author":"Graves","year":"1999","journal-title":"Nav. Res. Logist."},{"key":"ref_27","first-page":"2082","article-title":"Minimizing maximum earliness in single-machine scheduling with flexible maintenance time","volume":"24","author":"Ganji","year":"2017","journal-title":"Sci. Iran"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1335","DOI":"10.1016\/S0305-0548(02)00074-6","article-title":"Single-machine scheduling with periodic maintenance and nonresumable jobs","volume":"30","author":"Liao","year":"2003","journal-title":"Comput. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/j.omega.2008.01.001","article-title":"Minimizing number of tardy jobs on a single machine subject to periodic maintenance","volume":"37","author":"Chen","year":"2009","journal-title":"Omega"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2196","DOI":"10.1016\/j.cor.2011.11.002","article-title":"Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance","volume":"39","author":"Lee","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_31","first-page":"103","article-title":"Minimizing the number of tardy jobs on single machine scheduling with flexible maintenance time","volume":"50","author":"Ganji","year":"2018","journal-title":"J. Algorithm Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"2708","DOI":"10.1080\/00207543.2020.1737336","article-title":"A single machine scheduling problem with machine availability constraints and preventive maintenance","volume":"59","author":"Chen","year":"2020","journal-title":"Int. J. Prod. Res."},{"key":"ref_33","unstructured":"Johnson, D.S. (1973). Near-Optimal Bin Packing Algorithms. [Ph.D. Thesis, MIT]."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1080\/002075499192020","article-title":"Minimizing makespan on a single processing machine with dynamic job arrivals","volume":"37","author":"Lee","year":"1999","journal-title":"Int. J. Prod. Res."},{"key":"ref_35","first-page":"136","article-title":"Scheduling for a single semiconductor batch-processing machine to minimize total weighted tardiness","volume":"25","author":"Chou","year":"2010","journal-title":"J. Chin. Inst. Ind. Eng."},{"key":"ref_36","unstructured":"Holland, J.H. (1975). Adaptation in Natural and Artificial Systems, The University of Michigan Press."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"8804","DOI":"10.1016\/j.eswa.2011.01.091","article-title":"Intelligent bionic genetic algorithm (IB-GA) and its convergence","volume":"38","author":"Li","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Cobb, H.G., and Grefenstette, J.J. (1993, January 1). Genetic algorithms for tracking changing environments. Proceedings of the Fifth International Conference on Genetic Algorithms, San Francisco, CA, USA.","DOI":"10.21236\/ADA294075"},{"key":"ref_39","unstructured":"Yang, S. (2007). Workshops on Applications of Evolutionary Computation, Springer."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1750025","DOI":"10.1142\/S1469026817500250","article-title":"Immigrants based adaptive genetic algorithms for task allocation in multi-robot systems","volume":"16","author":"Muhuri","year":"2017","journal-title":"Int. J. Comput. Intell. Appl."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/4\/207\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:15:00Z","timestamp":1760123700000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/4\/207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,12]]},"references-count":40,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,4]]}},"alternative-id":["a16040207"],"URL":"https:\/\/doi.org\/10.3390\/a16040207","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,12]]}}}