Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates

DOI10.1016/S0167-6377(01)00099-2zbMath1018.90015WikidataQ127330129 ScholiaQ127330129MaRDI QIDQ5952071

David Simchi-Levi, Philip M. Kaminsky

Publication date: 8 January 2002

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

schedulingasymptotic analysison-line algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Related Items (10)

Effective on-line algorithms for reliable due date quotation and large-scale scheduling ⋮ A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection ⋮ The expected asymptotical ratio for preemptive stochastic online problem ⋮ Optimal control of a two-server flow-shop network ⋮ Coordinating a decentralized hybrid push-pull assembly system with unreliable supply and uncertain demand ⋮ Scheduling and due‐date quotation in a make‐to‐order supply chain ⋮ The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates ⋮ Almost sure asymptotic optimality for online routing and machine scheduling problems ⋮ An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time ⋮ Asymptotic analysis of online algorithms and improved scheme for the flow shop scheduling problem with release dates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• An algorithm for single machine sequencing with release dates to minimize total weighted completion time
• Scheduling with release dates on a single machine to minimize total weighted completion time
• A time indexed formulation of non-preemptive single machine scheduling problems
• Minimizing average completion time in the presence of release dates
• Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time Problem
• Scheduling of a single machine to minimize total weighted completion time subject to release dates
• The Asymptotic Optimality of the SPT Rule for the Flow Shop Mean Completion Time Problem
• Probabilistic Analysis of a Machine Scheduling Problem
• Sequencing Jobs with Unequal Ready Times to Minimize Mean Flow Time
• Optimal on-line algorithms for single-machine scheduling
• Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline

This page was built for publication: Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates