Complexity of Bilevel Scheduling Problems with Machine-Dependent Processing Times: Classical, Parameterized, and Approximation Perspectives

Complexity of Bilevel Scheduling Problems with Machine-Dependent Processing Times: Classical, Parameterized, and Approximation Perspectives | 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 Complexity of Bilevel Scheduling Problems with Machine-Dependent Processing Times: Classical, Parameterized, and Approximation Perspectives Yuqun Zhou This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8634926/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Bilevel scheduling captures hierarchical decision-making where a leader assigns jobs to machines and a follower sequences them, each optimizing distinct objectives. We provide a comprehensive complexity analysis for unrelated parallel machines with machine-dependent processing times, examining the problem through three complementary lenses: classical complexity, parameterized complexity, and approximability. Our main results establish that pessimistic bilevel scheduling is Σ₂ᴾ-complete, placing it at the second level of the polynomial hierarchy where no compact integer programming formulation exists unless unlikely complexity-theoretic collapses occur. We prove that the problem is W[1]-hard when parameterized by the number of machines, yet fixed-parameter tractable when parameterized by both machine count and maximum processing time. For the optimistic variant, we design a polynomial-time approximation scheme and prove APX-hardness, precisely characterizing its approximability. We identify polynomial-time solvable special cases including fixed machine count and agreeing processing time orders. These results bridge bilevel optimization, scheduling theory, and parameterized complexity, revealing how the hierarchical structure interacts with machine heterogeneity to determine computational tractability. Bilevel optimization Scheduling complexity Polynomial hierarchy Parameterized complexity Approximation algorithms Unrelated parallel machines Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted 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-8634926","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":578746243,"identity":"77806da0-8183-4bb2-9246-d48447c14f7a","order_by":0,"name":"Yuqun Zhou","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAz0lEQVRIiWNgGAWjYFACHiD+YcPMz8DYAOJCSIJaGHvS2CUbSNLCwHaI3+AAhEtYi8H5swcf8/AckDa+kdz84QeDjeyGA4S0HDiXbMxjccfY7EZim2QPQ5oxYS0He8ykeXieJZvdTmxjZmA4nEhYy2EeoBa2w/WbZyc2f2Zg+E+ElmMQLcwG0okN0gwMBwhrkTzDY2w4tyeNWeL+Q6BfDJKNZxLSwnf+jOGDN6Co7Dn++MOPCjvZPkJaFFAVGBBQDgLyDUQoGgWjYBSMghEOAJICRNaLXxhmAAAAAElFTkSuQmCC","orcid":"","institution":"University of Wisconsin–Madison","correspondingAuthor":true,"prefix":"","firstName":"Yuqun","middleName":"","lastName":"Zhou","suffix":""}],"badges":[],"createdAt":"2026-01-19 04:23:14","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8634926/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8634926/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":100958095,"identity":"f72e8b49-3101-4e28-957a-52887c522b2b","added_by":"auto","created_at":"2026-01-23 07:57:04","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":31996,"visible":true,"origin":"","legend":"","description":"","filename":"approximationlandscape.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/e02dd82e9db380d9e22614b0.pdf"},{"id":100958081,"identity":"1b2605f2-d950-4315-83e8-66d5046e2757","added_by":"auto","created_at":"2026-01-23 07:56:57","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":23550,"visible":true,"origin":"","legend":"","description":"","filename":"approximationratio.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/6c37f1c5a273505ef09756f3.pdf"},{"id":100958131,"identity":"64fc8030-b910-4d41-8843-91f2eeb40aa6","added_by":"auto","created_at":"2026-01-23 07:57:14","extension":"pdf","order_by":2,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":423550,"visible":true,"origin":"","legend":"","description":"","filename":"JOSComplexityofBilevelSchedulingProblemswithMachineDependentProcessingTimes.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/3ab9db1d78523fce95abd797.pdf"},{"id":100958093,"identity":"5185f99d-225d-46c0-ae5d-cbd03dea472b","added_by":"auto","created_at":"2026-01-23 07:57:04","extension":"pdf","order_by":3,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":33906,"visible":true,"origin":"","legend":"","description":"","filename":"bilevelstructure.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/f5f1ff3ee6756c026ae7a47f.pdf"},{"id":100958082,"identity":"ec18ea2f-91af-4112-b837-438be42322c4","added_by":"auto","created_at":"2026-01-23 07:56:57","extension":"pdf","order_by":4,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":19539,"visible":true,"origin":"","legend":"","description":"","filename":"complexitylandscape.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/5afb23efb9e9cda333d3c69d.pdf"},{"id":100958090,"identity":"348b9ec0-e0f8-42a6-a448-7d52317e1758","added_by":"auto","created_at":"2026-01-23 07:57:04","extension":"pdf","order_by":5,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":34617,"visible":true,"origin":"","legend":"","description":"","filename":"parameterizedlandscape.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/89f25be0373cede295418b7e.pdf"},{"id":100958125,"identity":"603f8ae4-b1ac-4809-9e30-fa84cccebaf9","added_by":"auto","created_at":"2026-01-23 07:57:12","extension":"pdf","order_by":6,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":38807,"visible":true,"origin":"","legend":"","description":"","filename":"reductiondiagram.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/4e21a017ea0b4a2377b3c4ad.pdf"},{"id":100958053,"identity":"883eab7f-6437-40bc-a03e-815dffee9163","added_by":"auto","created_at":"2026-01-23 07:56:50","extension":"pdf","order_by":7,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":25510,"visible":true,"origin":"","legend":"","description":"","filename":"runtimescaling.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/7d9c18311b2a390190290996.pdf"},{"id":100958109,"identity":"d2267bf7-4cb6-43b1-9df0-ea06657b2196","added_by":"auto","created_at":"2026-01-23 07:57:08","extension":"pdf","order_by":8,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":32932,"visible":true,"origin":"","legend":"","description":"","filename":"w1reduction.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/fa3b80050515f7a5ce9bb967.pdf"},{"id":100958103,"identity":"d56684a6-9b21-4f20-8253-2c8a2578bc14","added_by":"auto","created_at":"2026-01-23 07:57:07","extension":"json","order_by":9,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":3284,"visible":true,"origin":"","legend":"","description":"","filename":"c29325b2d45c4453a60515313e83491b.json","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/7e3e08ea9db03c2988fc7bba.json"},{"id":100958101,"identity":"a5124058-7f24-4eb1-882f-cd19254c79cd","added_by":"auto","created_at":"2026-01-23 07:57:06","extension":"py","order_by":10,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":40918,"visible":true,"origin":"","legend":"","description":"","filename":"bilevelscheduling.py","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1/e94ae73a7d7e3b5d2ea0e4e1.py"},{"id":100958165,"identity":"f9f21061-a0fc-4430-a9b9-f4ac53209832","added_by":"auto","created_at":"2026-01-23 07:57:18","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":333714,"visible":true,"origin":"","legend":"","description":"","filename":"JOSComplexityofBilevelSchedulingProblemswithMachineDependentProcessingTimes.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8634926/v1_covered_c9436edd-6dbd-40bc-935e-f414c6ea294b.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Complexity of Bilevel Scheduling Problems with Machine-Dependent Processing Times: Classical, Parameterized, and Approximation Perspectives","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Bilevel optimization, Scheduling complexity, Polynomial hierarchy, Parameterized complexity, Approximation algorithms, Unrelated parallel machines","lastPublishedDoi":"10.21203/rs.3.rs-8634926/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8634926/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Bilevel scheduling captures hierarchical decision-making where a leader assigns jobs to machines and a follower sequences them, each optimizing distinct objectives. We provide a comprehensive complexity analysis for unrelated parallel machines with machine-dependent processing times, examining the problem through three complementary lenses: classical complexity, parameterized complexity, and approximability. Our main results establish that pessimistic bilevel scheduling is Σ₂ᴾ-complete, placing it at the second level of the polynomial hierarchy where no compact integer programming formulation exists unless unlikely complexity-theoretic collapses occur. We prove that the problem is W[1]-hard when parameterized by the number of machines, yet fixed-parameter tractable when parameterized by both machine count and maximum processing time. For the optimistic variant, we design a polynomial-time approximation scheme and prove APX-hardness, precisely characterizing its approximability. We identify polynomial-time solvable special cases including fixed machine count and agreeing processing time orders. These results bridge bilevel optimization, scheduling theory, and parameterized complexity, revealing how the hierarchical structure interacts with machine heterogeneity to determine computational tractability.","manuscriptTitle":"Complexity of Bilevel Scheduling Problems with Machine-Dependent Processing Times: Classical, Parameterized, and Approximation Perspectives","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-01-23 07:55:04","doi":"10.21203/rs.3.rs-8634926/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"c714242c-35cd-4980-b6d8-0f93b7d872f9","owner":[],"postedDate":"January 23rd, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2026-01-23T07:55:04+00:00","versionOfRecord":[],"versionCreatedAt":"2026-01-23 07:55:04","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8634926","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8634926","identity":"rs-8634926","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}