Lower and upper bounds for the preemptive single machine scheduling problem with equal processing times

DOI10.1007/978-1-4614-8588-9_2zbMATH Open1344.90020OpenAlexW1596128MaRDI QIDQ2820105FDOQ2820105

Authors Mikhail Batsyn, Pavel Sukhov, Boris Goldengorin, Panos M. Pardalos 

Publication date 13 September 2016

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-1-4614-8588-9_2

zbMATH Keywords

assignment problemlower boundsingle machine schedulingupper boundrelease datesequal processing timesweighted completion time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 4191384
• Properties of optimal schedules for the minimization total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine
• An exact algorithm for the preemptive single machine scheduling of equal-length jobs
• Preemptive scheduling of equal-length jobs in polynomial time
• Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times

Cites work

• scientific article; zbMATH DE number 3883931 (Why is no real title available?)
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• A 1. 47-approximation for a preemptive single-machine scheduling problem
• A classification of static scheduling problems
• A polytime algorithm based on a primal LP model for the scheduling problem \(1|pmtn;p_j=2;r_j|\sum w_jC_j\)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling equal-length jobs on identical parallel machines
• Scheduling jobs with equal processing times and time windows on identical parallel machines
• Scheduling. Theory, algorithms, and systems.

Cited in

(9)

• An exact algorithm for the preemptive single machine scheduling of equal-length jobs
• Preemptive scheduling of equal-length jobs in polynomial time
• Modeling single machine preemptive scheduling problems for computational efficiency
• Properties of optimal schedules for the minimization total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine
• Improving the preemptive bound for the single machine dynamic maximum lateness problem
• scientific article; zbMATH DE number 4191384 (Why is no real title available?)
• Single parameter analysis of power of preemption on two and three uniform machines
• Improving the preemptive bound for the one-machine dynamic total completion time scheduling problem.
• scientific article; zbMATH DE number 432995 (Why is no real title available?)

This page was built for publication: Lower and upper bounds for the preemptive single machine scheduling problem with equal processing times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2820105)