On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
We consider the stochastic single-machine problem, when the objective is to minimize the expected total weighted completion time of a set of jobs that are released over time. We assume that the existence and the parameters of each job including its release date, weight, and expected processing times are not known until its release date. The actual processing times are not known until processing is completed. We analyze the performance of the on-line nonpreemptive weighted shortest expected processing time among available jobs (WSEPTA) heuristic. When a scheduling decision needs to be made, this heuristic assigns, among the jobs that have arrived but not yet processed, one with the largest ratio of its weight to its expected processing time. We prove that when the job weights and processing times are bounded and job processing times are mutually independent random variables, WSEPTA is asymptotically optimal for the single-machine problem. This implies that WSEPTA generates a solution whose relative error approaches zero as the number of jobs increases. This result can be extended to the stochastic flow shop and open shop problems, as well as models with stochastic job weights.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.001 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it