New and improved algorithms for minsum shop scheduling
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 a general class of multiprocessor shop scheduling problems with a minsum objective, and present approximation methods based on linear programming relaxations in the operation completion times. These LP relaxations use new classes of valid inequalities for multistage jobs. We first consider open shop problems with total weighted job completion time objective. For the nonpreemptive problem Ojj P w j C j , we introduce "LP-based precedence constraints" and derive a 5.83-approximation algorithm. For its preemptive version, Ojpmtnj P w j C j , we show that a simple job-based greedy algorithm, using directly the LP solution, yields a 3approximation. We then consider a general class of multiprocessor shop scheduling problems, preemptive or nonpreemptive, with precedence constraints between operations, with job or operation release dates, and with a general minsum objective. This class of objectives includes, among others, weighted sums of operations completion times, job comp...
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.000 | 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.000 | 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.001 | 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