{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:52:24Z","timestamp":1753887144819,"version":"3.41.2"},"reference-count":37,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,7,9]]},"abstract":"Abstract<\/jats:title>\n Let \n \n \n \n \u03b1<\/m:mi>\n <\/m:math>\n \\alpha <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> be a set of \n \n \n \n n<\/m:mi>\n <\/m:math>\n n<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> elements and \n \n \n \n \u03b4<\/m:mi>\n <\/m:math>\n \\delta <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> be a nonnegative integer. A \n \n \n \n \u03b4<\/m:mi>\n <\/m:math>\n \\delta <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-partition of \n \n \n \n \u03b1<\/m:mi>\n <\/m:math>\n \\alpha <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is a set of pairwise disjoint nonempty subsets of \n \n \n \n \u03b1<\/m:mi>\n <\/m:math>\n \\alpha <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that the union of the subsets is equal to \n \n \n \n \u03b1<\/m:mi>\n <\/m:math>\n \\alpha <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and every subset has a size greater than \n \n \n \n \u03b4<\/m:mi>\n <\/m:math>\n \\delta <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. We formulate an algorithm for computing all \n \n \n \n \u03b4<\/m:mi>\n <\/m:math>\n \\delta <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-partitions of a given \n \n \n \n n<\/m:mi>\n <\/m:math>\n n<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-element set and show that the algorithm runs in \n \n \n \n O<\/m:mi>\n \n (<\/m:mo>\n \n n<\/m:mi>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:math>\n {\\mathcal{O}}\\left(n)<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> space and \n \n \n \n O<\/m:mi>\n \n (<\/m:mo>\n \n n<\/m:mi>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:math>\n {\\mathcal{O}}\\left(n)<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n delay<\/jats:italic> time between any two successive outputs of \n \n \n \n \u03b4<\/m:mi>\n <\/m:math>\n \\delta <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-partitions of the given set. An application of the notion of \n \n \n \n \u03b4<\/m:mi>\n <\/m:math>\n \\delta <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-partitions is illustrated in the following scheduling problem. Suppose a factory has \n \n \n \n n<\/m:mi>\n <\/m:math>\n n<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> machines and \n \n \n \n m<\/m:mi>\n \u2264<\/m:mo>\n n<\/m:mi>\n <\/m:math>\n m\\le n<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> jobs to complete daily. Every job can be accomplished by operating at least \n \n \n \n \u03b4<\/m:mi>\n +<\/m:mo>\n 1<\/m:mn>\n <\/m:math>\n \\delta +1<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> machines. A machine cannot work on multiple jobs simultaneously. According to a utilization policy of the factory\u2019s management, no machine is allowed to be idle, so all machines should be running on some job. Find a daily schedule of the factory\u2019s machines satisfying all the mentioned constraints. Let \n \n \n \n \u03b1<\/m:mi>\n <\/m:math>\n \\alpha <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> be the set of the factory\u2019s machines. Then, an \n \n \n \n \u03b1<\/m:mi>\n <\/m:math>\n \\alpha <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\u2019s \n \n \n \n \u03b4<\/m:mi>\n <\/m:math>\n \\delta <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-partition with \n \n \n \n m<\/m:mi>\n <\/m:math>\n m<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> subsets is a legal schedule if every subset (in the \n \n \n \n \u03b4<\/m:mi>\n <\/m:math>\n \\delta <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-partition) includes exclusively \n \n \n \n \u03b4<\/m:mi>\n +<\/m:mo>\n 1<\/m:mn>\n <\/m:math>\n \\delta +1<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> or more machines that run on the same job.<\/jats:p>","DOI":"10.1515\/comp-2024-0011","type":"journal-article","created":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T07:37:03Z","timestamp":1723102623000},"source":"Crossref","is-referenced-by-count":0,"title":["Listing all delta partitions of a given set: Algorithm design and results"],"prefix":"10.1515","volume":"14","author":[{"given":"Samer","family":"Nofal","sequence":"first","affiliation":[{"name":"Department of Computer Science, German Jordanian University , Amman , Jordan"}]}],"member":"374","published-online":{"date-parts":[[2024,7,9]]},"reference":[{"key":"2024080807314791516_j_comp-2024-0011_ref_001","doi-asserted-by":"crossref","unstructured":"J. Snauwaert and M. Vanhoucke, \u201cA classification and new benchmark instances for the multi-skilled resource-constrained project scheduling problem,\u201d Europ. J. Operat. Res., vol. 307, no. 1, pp. 1\u201319, 2023.","DOI":"10.1016\/j.ejor.2022.05.049"},{"key":"2024080807314791516_j_comp-2024-0011_ref_002","doi-asserted-by":"crossref","unstructured":"S. Zhang, Z. Zhou, R. Luo, R. Zhao, Y. Xiao, and Y. Xu, \u201cA low-carbon, fixed-tour scheduling problem with time windows in a time-dependent traffic environment,\u201d Int. J. Production Res., vol. 61, no. 18, pp. 6177\u20136196, 2023.","DOI":"10.1080\/00207543.2022.2153940"},{"key":"2024080807314791516_j_comp-2024-0011_ref_003","doi-asserted-by":"crossref","unstructured":"D. B. Fontes, S. M. Homayouni, and J. F. Gon\u00e7alves, \u201cA hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources,\u201d Europ. J. Operat. Res., vol. 306, no. 3, pp. 1140\u20131157, 2023.","DOI":"10.1016\/j.ejor.2022.09.006"},{"key":"2024080807314791516_j_comp-2024-0011_ref_004","doi-asserted-by":"crossref","unstructured":"A. Goli, A. Ala, and M. Hajiaghaei-Keshteli, \u201cEfficient multi-objective meta-heuristic algorithms for energy-aware non-permutation flow-shop scheduling problem,\u201d Expert Syst. Appl., vol. 213, p. 119077, 2023.","DOI":"10.1016\/j.eswa.2022.119077"},{"key":"2024080807314791516_j_comp-2024-0011_ref_005","doi-asserted-by":"crossref","unstructured":"W. Wang, G. Tian, H. Zhang, Z. Li, and L. Zhang, \u201cA hybrid genetic algorithm with multiple decoding methods for energy-aware remanufacturing system scheduling problem,\u201d Robotics Comput-Integrated Manufacturing, vol. 81, p. 102509, 2023.","DOI":"10.1016\/j.rcim.2022.102509"},{"key":"2024080807314791516_j_comp-2024-0011_ref_006","doi-asserted-by":"crossref","unstructured":"I. Hayat, A. Tariq, W. Shahzad, M. Masud, S. Ahmed, M. U. Ali, and A. Zafar, \u201cHybridization of particle swarm optimization with variable neighborhood search and simulated annealing for improved handling of the permutation flow-shop scheduling problem,\u201d Systems, vol. 11, no. 5, p. 221, 2023.","DOI":"10.3390\/systems11050221"},{"key":"2024080807314791516_j_comp-2024-0011_ref_007","doi-asserted-by":"crossref","unstructured":"K. Gkiotsalitis, C. Iliopoulou, and K. Kepaptsoglou, \u201cAn exact approach for the multi-depot electric bus scheduling problem with time windows,\u201d Europ. J. Operat. Res., vol. 306, no. 1, pp. 189\u2013206, 2023.","DOI":"10.1016\/j.ejor.2022.07.017"},{"key":"2024080807314791516_j_comp-2024-0011_ref_008","doi-asserted-by":"crossref","unstructured":"F. Mischek, N. Musliu, and A. Schaerf, \u201cLocal search approaches for the test laboratory scheduling problem with variable task grouping,\u201d J. Scheduling, vol. 26, pp. 1\u201321, 2021.","DOI":"10.1007\/s10951-021-00699-2"},{"key":"2024080807314791516_j_comp-2024-0011_ref_009","doi-asserted-by":"crossref","unstructured":"K. Sylejmani, E. Gashi, and A. Ymeri, \u201cSimulated annealing with penalization for university course timetabling,\u201d J. Scheduling, vol. 26, pp. 1\u201321, 2022.","DOI":"10.1007\/s10951-022-00747-5"},{"key":"2024080807314791516_j_comp-2024-0011_ref_010","doi-asserted-by":"crossref","unstructured":"D. M. Utama and C. N. Al Imron, \u201cA systematic literature review on no-idle flow shop scheduling problem,\u201d Oper. Res. Forum., vol. 5, no. 1, 2024, p. 18.","DOI":"10.1007\/s43069-024-00304-0"},{"key":"2024080807314791516_j_comp-2024-0011_ref_011","doi-asserted-by":"crossref","unstructured":"Z. Bahroun, R. As\u2019ad, M. Tanash, and R. Athamneh, \u201cThe multi-skilled resource-constrained project scheduling problem: A systematic review and an exploration of future landscapes,\u201d Manag. Syst. Production Eng., vol. 32, no. 1, pp. 108\u2013132, 2024.","DOI":"10.2478\/mspe-2024-0012"},{"key":"2024080807314791516_j_comp-2024-0011_ref_012","doi-asserted-by":"crossref","unstructured":"S. B. Shargh, M. Zandieh, A. Ayough, and F. Farhadi, \u201cScheduling in services: a review and bibliometric analysis,\u201d Operations Management Research, pp. 1\u201330, 2024.","DOI":"10.1007\/s12063-024-00469-1"},{"key":"2024080807314791516_j_comp-2024-0011_ref_013","doi-asserted-by":"crossref","unstructured":"Y. Xu, S. Wandelt, and X. Sun, \u201cAirline scheduling optimization: literature review and a discussion of modelling methodologies,\u201d Intelligent Transport. Infrastruct., vol. 3, p. liad026, 2024.","DOI":"10.1093\/iti\/liad026"},{"key":"2024080807314791516_j_comp-2024-0011_ref_014","doi-asserted-by":"crossref","unstructured":"J. Pasha, B. Li, Z. Elmi, A. M. Fathollahi-Fard Y.-y. Lau, A. Roshani, T. Kawasaki, et al., \u201cElectric vehicle scheduling: State of the art, critical challenges, and future research opportunities,\u201d J. Industr. Inform. Integration, vol. 38, p. 100561, 2024.","DOI":"10.1016\/j.jii.2024.100561"},{"key":"2024080807314791516_j_comp-2024-0011_ref_015","doi-asserted-by":"crossref","unstructured":"M. Khakifirooz, M. Fathi, A. Dolgui, and P. M. Pardalos, \u201cScheduling in industrial environment toward future: insights from jean-marie proth,\u201d Int. J. Production Res., vol. 62, no. 1\u20132, pp. 291\u2013317, 2024.","DOI":"10.1080\/00207543.2023.2245919"},{"key":"2024080807314791516_j_comp-2024-0011_ref_016","doi-asserted-by":"crossref","unstructured":"M. Aghileh, A. Tereso, F. Alvelos, and M. O. Monteiro Lopes, \u201cMulti-project scheduling under uncertainty and resource flexibility: a systematic literature review,\u201d Prod. Manuf. Res., vol. 12, no. 1, p. 2319574, 2024.","DOI":"10.1080\/21693277.2024.2319574"},{"key":"2024080807314791516_j_comp-2024-0011_ref_017","doi-asserted-by":"crossref","unstructured":"E. Aktasss, H. Atmaca, and H. Akbulut, \u201c\u2018Operating room and surgical team members scheduling: A comprehensive review,\u201d J. Project Management, vol. 9, no. 2, pp. 149\u2013162, 2024.","DOI":"10.5267\/j.jpm.2023.12.001"},{"key":"2024080807314791516_j_comp-2024-0011_ref_018","doi-asserted-by":"crossref","unstructured":"J. Culver and A. J. Weingartner, \u201cSet partitions without blocks of certain sizes,\u201d Eur. J. Comb., vol. 84, p. 103041, 2020.","DOI":"10.1016\/j.ejc.2019.103041"},{"key":"2024080807314791516_j_comp-2024-0011_ref_019","unstructured":"T. C. Hu and M. Shing, Combinatorial Algorithms: Enlarged, Second Edition, Courier Corporation, New York, USA, 2012."},{"key":"2024080807314791516_j_comp-2024-0011_ref_020","doi-asserted-by":"crossref","unstructured":"I. Mezo, Combinatorics and number theory of counting sequences, Chapman and Hall\/CRC, Florida, USA, 2019.","DOI":"10.1201\/9781315122656"},{"key":"2024080807314791516_j_comp-2024-0011_ref_021","doi-asserted-by":"crossref","unstructured":"T. Mansour, Combinatorics of Set Partitions. Boca Raton, CRC Press, 2013.","DOI":"10.1201\/b12691"},{"key":"2024080807314791516_j_comp-2024-0011_ref_022","doi-asserted-by":"crossref","unstructured":"C. Savage, \u201cA survey of combinatorial gray codes,\u201d SIAM review, vol. 39, no. 4, pp. 605\u2013629, 1997.","DOI":"10.1137\/S0036144595295272"},{"key":"2024080807314791516_j_comp-2024-0011_ref_023","doi-asserted-by":"crossref","unstructured":"D. L. Kreher and D. R. Stinson, \u201cCombinatorial algorithms: generation, enumeration, and search,\u201d ACM SIGACT News, vol. 30, no. 1, pp. 33\u201335, 1999.","DOI":"10.1145\/309739.309744"},{"key":"2024080807314791516_j_comp-2024-0011_ref_024","unstructured":"A. Nijenhuis and H. S. Wilf, Combinatorial algorithms: for computers and calculators. Elsevier, 2014."},{"key":"2024080807314791516_j_comp-2024-0011_ref_025","doi-asserted-by":"crossref","unstructured":"G. Hutchinson, \u201cPartioning algorithms for finite sets,\u201d Commun. ACM, vol. 6, no. 10, pp. 613\u2013614, 1963.","DOI":"10.1145\/367651.367661"},{"key":"2024080807314791516_j_comp-2024-0011_ref_026","doi-asserted-by":"crossref","unstructured":"G. Ehrlich, \u201cLoopless algorithms for generating permutations, combinations, and other combinatorial configurations,\u201d J. ACM, vol. 20, no. 3, pp. 500\u2013513, 1973.","DOI":"10.1145\/321765.321781"},{"key":"2024080807314791516_j_comp-2024-0011_ref_027","doi-asserted-by":"crossref","unstructured":"R. Kaye, \u201cA gray code for set partitions,\u201d Inf. Process. Lett., vol. 5, no. 6, pp. 171\u2013173, 1976.","DOI":"10.1016\/0020-0190(76)90014-4"},{"key":"2024080807314791516_j_comp-2024-0011_ref_028","doi-asserted-by":"crossref","unstructured":"F. Ruskey, \u201cSimple combinatorial gray codes constructed by reversing sublists,\u201d in Algorithms and Computation, 4th International Symposium Proceedings, ser. Lecture Notes in Computer Science, K. Ng, P. Raghavan, N. V. Balasubramanian, and F. Y. L. Chin, Eds., vol. 762, Springer, New York, USA, 1993, pp. 201\u2013208.","DOI":"10.1007\/3-540-57568-5_250"},{"key":"2024080807314791516_j_comp-2024-0011_ref_029","doi-asserted-by":"crossref","unstructured":"M. C. Er, \u201cA fast algorithm for generating set partitions,\u201d Comput. J., vol. 31, no. 3, pp. 283\u2013284, 1988.","DOI":"10.1093\/comjnl\/31.3.283"},{"key":"2024080807314791516_j_comp-2024-0011_ref_030","doi-asserted-by":"crossref","unstructured":"B. Djokic, M. Miyakawa, S. Sekiguchi, I. Semba, and I. Stojmenovic, \u201cA fast iterative algorithm for generating set partitions,\u201d Comput. J., vol. 32, no. 3, pp. 281\u2013282, 1989.","DOI":"10.1093\/comjnl\/32.3.281"},{"key":"2024080807314791516_j_comp-2024-0011_ref_031","doi-asserted-by":"crossref","unstructured":"T. Mansour and G. Nassar, \u201cGray codes, loopless algorithm and partitions,\u201d J. Math. Model. Algorithms, vol. 7, no. 3, pp. 291\u2013310, 2008.","DOI":"10.1007\/s10852-008-9086-9"},{"key":"2024080807314791516_j_comp-2024-0011_ref_032","doi-asserted-by":"crossref","unstructured":"Z. Kokosi\u0144ski, \u201cA new algorithm for generation of exactly m-block set partitions in associative model,\u201d Lecture Notes in Computer Science, vol. 3911 LNCS, 2006, pp. 67\u201374.","DOI":"10.1007\/11752578_9"},{"key":"2024080807314791516_j_comp-2024-0011_ref_033","doi-asserted-by":"crossref","unstructured":"W. Lee, J. Tsay, H. Chen, and T. Tseng, \u201cAn optimal systolic algorithm for the set partitioning problem, Parallel Algorithms Appl., vol. 10, no. 3\u20134, pp. 301\u2013313, 1997.","DOI":"10.1080\/10637199708915624"},{"key":"2024080807314791516_j_comp-2024-0011_ref_034","doi-asserted-by":"crossref","unstructured":"A. Williams, \u201cThe greedy gray code algorithm,\u201d in Algorithms and Data Structures, 13th International Symposium Proceedings, ser. Lecture Notes in Computer Science, F. Dehne, R. Solis-Oba, and J. Sack, Eds., vol. 8037. Springer, 2013, pp. 525\u2013536.","DOI":"10.1007\/978-3-642-40104-6_46"},{"key":"2024080807314791516_j_comp-2024-0011_ref_035","doi-asserted-by":"crossref","unstructured":"C. Huemer, F. Hurtado, M. Noy, and E. Oma\u00f1a-Pulido, \u201cGray codes for non-crossing partitions and dissections of a convex polygon,\u201d Discrete Appl. Math., vol. 157, no. 7, pp. 1509\u20131520, 2009.","DOI":"10.1016\/j.dam.2008.06.018"},{"key":"2024080807314791516_j_comp-2024-0011_ref_036","doi-asserted-by":"crossref","unstructured":"A. Conflitti and R. Mamede, \u201cGray codes and lexicographical combinatorial generation for nonnesting and sparse nonnesting set partitions,\u201d Theor. Comput. Sci., vol. 592, pp. 87\u201396, 2015.","DOI":"10.1016\/j.tcs.2015.05.021"},{"key":"2024080807314791516_j_comp-2024-0011_ref_037","doi-asserted-by":"crossref","unstructured":"A. Conflitti and R. Mamede, \u201cGray codes for noncrossing and nonnesting partitions of classical types,\u201d IJAC, vol. 27, no. 5, pp. 455\u2013476, 2017.","DOI":"10.1142\/S0218196717500230"}],"container-title":["Open Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2024-0011\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2024-0011\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T07:37:17Z","timestamp":1723102637000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2024-0011\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,1]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,7,9]]},"published-print":{"date-parts":[[2024,7,9]]}},"alternative-id":["10.1515\/comp-2024-0011"],"URL":"https:\/\/doi.org\/10.1515\/comp-2024-0011","relation":{},"ISSN":["2299-1093"],"issn-type":[{"type":"electronic","value":"2299-1093"}],"subject":[],"published":{"date-parts":[[2024,1,1]]},"article-number":"20240011"}}