Fair Repetitive Interval Scheduling

Fair Repetitive Interval Scheduling | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Fair Repetitive Interval Scheduling Klaus Heeger, Danny Hermelin, Yuval Itzhaki, Hendrik Molter, Dvir Shabtay This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4673329/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 26 May, 2025 Read the published version in Algorithmica → Version 1 posted 7 You are reading this latest preprint version Abstract Fair resource allocation is undoubtedly a crucial factor in customer satisfaction in several scheduling scenarios. This is especially apparent in repetitive scheduling models where the same set of clients repeatedly submits jobs on a daily basis. In this paper, we aim to analyze a repetitive scheduling system involving a set of $n$ clients and a set of $m$ days. On every day, each client submits a request to process a job exactly within a specific time interval, which may vary from day to day, modeling the scenario where the scheduling is done Just-In-Time (JIT). The daily schedule is executed on a single machine that can process a single job at a time, therefore it is not possible to schedule jobs with intersecting time intervals. Accordingly, a feasible solution corresponds to sets of jobs with disjoint time intervals, one set per day. We define the quality of service (QoS) that a client receives as the number of executed jobs over the $m$ days period. Our objective is to provide a feasible solution where each client has at least $k$ days where his jobs are processed. We prove that this problem is NP-hard even under various natural restrictions such as identical processing times and day-independent due dates. We also provide efficient algorithms for several special cases and analyze the parameterized tractability of the problem with respect to several parameters, providing both parameterized hardness and tractability results. Just-in-time Scheduling Interval Scheduling Algorithms Graph Theory Parameterized Complexity Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 26 May, 2025 Read the published version in Algorithmica → Version 1 posted Editorial decision: Revision requested 19 Dec, 2024 Reviews received at journal 10 Oct, 2024 Reviewers agreed at journal 18 Sep, 2024 Reviewers invited by journal 17 Jul, 2024 Editor assigned by journal 12 Jul, 2024 Submission checks completed at journal 05 Jul, 2024 First submitted to journal 02 Jul, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4673329","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":329489142,"identity":"f3f0bfca-8386-4216-9391-901b1cfaf6dd","order_by":0,"name":"Klaus Heeger","email":"","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":false,"prefix":"","firstName":"Klaus","middleName":"","lastName":"Heeger","suffix":""},{"id":329489143,"identity":"2b57d074-be10-4bdd-b42b-2012caf3d584","order_by":1,"name":"Danny Hermelin","email":"","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":false,"prefix":"","firstName":"Danny","middleName":"","lastName":"Hermelin","suffix":""},{"id":329489144,"identity":"8566fa88-43fa-4cad-974a-e6fc20a7d9fd","order_by":2,"name":"Yuval Itzhaki","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAw0lEQVRIiWNgGAWjYBACNghlIWcAFeDhI6gFokfCGK6FjUhrJBI3oNmLG/DJ95hJ89RIpG/nX2PA8KOGQYagFjY2HqCWYxK5O2e8MWDsOUaEw0BaJGewSeRuuHHGgIG3gWgt/yTSDYBaGP8Sq0XiY5tEgsH5HgNmIm1JK7b42CdhuHMGW8FhmWMShLXINx/eeCPhm428Of/hjQ/f1NjY8xPSwsDAAY1EiQSGA0CSsAYGBvYHEJr/ADGqR8EoGAWjYCQCAPblL6SLwVR2AAAAAElFTkSuQmCC","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":true,"prefix":"","firstName":"Yuval","middleName":"","lastName":"Itzhaki","suffix":""},{"id":329489145,"identity":"7da73e7e-91c2-449f-a6a8-8d1a666d9530","order_by":3,"name":"Hendrik Molter","email":"","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":false,"prefix":"","firstName":"Hendrik","middleName":"","lastName":"Molter","suffix":""},{"id":329489146,"identity":"76c456d5-9f25-4eac-bb49-32f7110a3bfb","order_by":4,"name":"Dvir Shabtay","email":"","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":false,"prefix":"","firstName":"Dvir","middleName":"","lastName":"Shabtay","suffix":""}],"badges":[],"createdAt":"2024-07-02 10:01:11","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4673329/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4673329/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s00453-025-01322-y","type":"published","date":"2025-05-26T15:57:58+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":83782989,"identity":"664b8877-3007-48c6-9486-b72814123a9b","added_by":"auto","created_at":"2025-06-02 16:09:41","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":526062,"visible":true,"origin":"","legend":"","description":"","filename":"fairrepetitivescheduling.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4673329/v1_covered_54a1e7b1-bdea-462a-8512-154d3a589430.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Fair Repetitive Interval Scheduling","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"algorithmica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"algo","sideBox":"Learn more about [Algorithmica](http://link.springer.com/journal/453)","snPcode":"453","submissionUrl":"https://submission.nature.com/new-submission/453/3","title":"Algorithmica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Just-in-time Scheduling, Interval Scheduling, Algorithms, Graph Theory, Parameterized Complexity","lastPublishedDoi":"10.21203/rs.3.rs-4673329/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4673329/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Fair resource allocation is undoubtedly a crucial factor in customer satisfaction in several scheduling scenarios. This is especially apparent in repetitive scheduling models where the same set of clients repeatedly submits jobs on a daily basis. In this paper, we aim to analyze a repetitive scheduling system involving a set of $n$ clients and a set of $m$ days. On every day, each client submits a request to process a job exactly within a specific time interval, which may vary from day to day, modeling the scenario where the scheduling is done Just-In-Time (JIT). The daily schedule is executed on a single machine that can process a single job at a time, therefore it is not possible to schedule jobs with intersecting time intervals. Accordingly, a feasible solution corresponds to sets of jobs with disjoint time intervals, one set per day. We define the quality of service (QoS) that a client receives as the number of executed jobs over the $m$ days period. Our objective is to provide a feasible solution where each client has at least $k$ days where his jobs are processed. We prove that this problem is NP-hard even under various natural restrictions such as identical processing times and day-independent due dates. We also provide efficient algorithms for several special cases and analyze the parameterized tractability of the problem with respect to several parameters, providing both parameterized hardness and tractability results.","manuscriptTitle":"Fair Repetitive Interval Scheduling","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-07-30 16:51:59","doi":"10.21203/rs.3.rs-4673329/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-12-20T03:49:57+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-10-10T20:15:11+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"337190965995795133988525626386016804334","date":"2024-09-18T04:28:26+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-07-17T18:33:29+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-07-12T04:14:00+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-07-05T10:43:24+00:00","index":"","fulltext":""},{"type":"submitted","content":"Algorithmica","date":"2024-07-02T09:59:58+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"algorithmica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"algo","sideBox":"Learn more about [Algorithmica](http://link.springer.com/journal/453)","snPcode":"453","submissionUrl":"https://submission.nature.com/new-submission/453/3","title":"Algorithmica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"684fa51e-666f-4537-8cf0-cfb014d7ee65","owner":[],"postedDate":"July 30th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-06-02T16:03:52+00:00","versionOfRecord":{"articleIdentity":"rs-4673329","link":"https://doi.org/10.1007/s00453-025-01322-y","journal":{"identity":"algorithmica","isVorOnly":false,"title":"Algorithmica"},"publishedOn":"2025-05-26 15:57:58","publishedOnDateReadable":"May 26th, 2025"},"versionCreatedAt":"2024-07-30 16:51:59","video":"","vorDoi":"10.1007/s00453-025-01322-y","vorDoiUrl":"https://doi.org/10.1007/s00453-025-01322-y","workflowStages":[]},"version":"v1","identity":"rs-4673329","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4673329","identity":"rs-4673329","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}