{"id":"543ab374-4979-499d-b0b9-5b8bbe77c284","arxiv_id":"1908.04452","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The authors adapt aggregative, Pareto, and NSGA-II genetic algorithms to the tri-objective P2|fixj,rj|Cmax,ΣTj,ΣCj problem and propose lower bounds for each objective.","lead":"This paper tests three genetic algorithm variants for scheduling tasks on two dedicated processors while simultaneously minimizing makespan, total tardiness, and total completion time. It also proposes lower bounds for each objective; on random instances, each variant wins on a different goal.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"LBTC is actually valid, but the 'effectiveness' claim lacks exact validation; tardiness ratios up to ~100 make the lower-bound-only evidence insufficient.","rationale":"The reader's weakest_assumption pins the paper's validity on LBTC. I checked the algebra in Section 3.4 and it is correct: the weighted split construction gives a lower bound because the relaxed problem can be scheduled contiguously to recover the original completion times minus a constant; the p_j/4 penalty is exactly that constant. Hence LBTC is a valid lower bound and the reader's concern does not translate into a correctness error. However, the paper still claims effectiveness, and the only evidence for this is the distance to lower bounds. The lower bounds for tardiness are evidently very loose or the solutions are very poor; either way TT/LBTT ratios up to ~100 cannot support effectiveness. The same issue, to a lesser degree, affects TC/LBTC and C/LBC because nothing establishes bound tightness. Since the instance sizes are tiny (n=10, 20), exact verification is cheap and should have been reported. This is a standard 'missing baseline' problem, not a fraud issue; it is exactly what the CONDITIONAL verdict should require. The proposed test would settle both whether the lower bound actually holds on all tested instances and whether the algorithms are near-optimal.","tokens_in":18101,"tokens_out":23213,"duration_ms":212989,"concrete_test":"Take the 150 n=10 instances (5 types × 3 α × 10 repeats) and solve each as three single-objective MIPs from Section 3.2 (minimize Cmax, ΣTj, ΣCj separately) using CPLEX. For every instance, compute the optimal Pareto front (or at least the three individual optima), compare each GA variant's best values to these optima, and check LBTC ≤ optimal ΣCj. If average relative gaps to optima are small (e.g., ≤5%) and LBTC never exceeds the optimal ΣCj, the effectiveness claim and lower bound stand; otherwise the paper's central assertion fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.4's LBTC construction is, on inspection, a valid relaxation: for any feasible original schedule, scheduling each split mono-job's two halves contiguously yields a relaxed schedule whose weighted objective is ΣC_j − Σ_{mono} p_j/4, so adding the p_j/4 penalty restores the original objective. Therefore optimal_relaxed + penalty ≤ any original ΣC_j, and LBTC is a genuine lower bound. The reader's specific concern does not land. The load-bearing weakness is instead that every quality claim is an indirect ratio to lower bounds of unmeasured tightness. For total tardiness, TT/LBTT reaches 99.889 (Table 9, aggregative, Type 2, α=1.5). If LBTT were tight, the algorithms would be ineffective on that criterion; if LBTT is loose, the ratio says nothing about solution quality. No comparison to exact optima or to an existing benchmark is provided, even though n=10–20 is small enough for exact MIP solving. The abstract's blanket 'effectiveness' is therefore underdetermined by the evidence, regardless of LBTC's validity.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the tri-objective scheduling problem P2|fixj,rj|Cmax,ΣTj,ΣCj on two dedicated processors. It proposes three genetic algorithm variants: an aggregative method using uniform-design weights, a Pareto-based method, and NSGA-II. It also presents lower bounds for the three criteria (LBC for makespan, LBTC for total completion time, LBTT for total tardiness) and evaluates the algorithms on randomly generated instances with n=10 and n=20 across five problem types and three release-date ranges. The evaluation uses ratios of each objective to its lower bound, the number of non-dominated solutions, and a hypervolume ratio. The abstract and conclusion claim that the proposed algorithms are effective.","tokens_in":18281,"tokens_out":7958,"duration_ms":78883,"significance":"If the computational results were fully supported, the paper would make a useful contribution: a practical multi-objective heuristic study for an NP-hard scheduling problem, together with a new lower bound LBTC for the total completion time criterion. A strength is that the relative ranking of the three algorithms is internally coherent, since all comparisons use the same lower-bound baselines, and the LBTC construction is, on inspection, a valid relaxation: scheduling the two halves of each mono-processor task contiguously in any feasible original schedule yields a relaxed schedule whose weighted objective is ΣC_j − Σp_j/4 for the mono-processor tasks, so adding the p_j/4 penalty restores a valid lower bound. However, the manuscript does not provide this proof, and more importantly, it offers no validation against exact optima or against existing benchmarks. The problem sizes considered (n=10 and n=20) are small enough that exact MIP or branch-and-bound results should be obtainable for at least a subset of instances.","major_comments":[{"comment":"The absolute quality of the solutions is measured only by ratios to lower bounds whose tightness is never established. For example, Table 9 reports TT/LBTT = 99.889 for Type 2, α=1.5 with the aggregative method; this could mean either that the solutions are very poor for the total tardiness criterion or that LBTT is very weak. Similarly, TC/LBTC values above 2.0 in Tables 9–11 could reflect a loose bound rather than a poor front. Since the instances have only n=10 or n=20 jobs, exact methods are feasible: one could solve the single-criterion problems exactly (e.g., a MIP solver or the branch-and-bound of Manaa and Chu [33] for makespan, and analogous exact methods for the other criteria) and report true optimality gaps on at least a subset of instances. Without this, the abstract's statement that the obtained results show 'the effectiveness of the proposed algorithms' is not supported, even though the relative ordering of the three algorithms is largely unaffected by bound tightness.","section":"§5.2, Tables 6–11"},{"comment":"The definition of the hypervolume ratio HVr is incomplete and, as written, appears incoherent. The formula HVr = 1 − (HV_LB − HV_Algorithm)/HV_LB requires an object HV_LB, which is never defined in the text. In the usual definition, the hypervolume of a single lower-bound point is zero, and if the lower bound is instead used as the reference point, the denominator vanishes. The text earlier states that the reference point is the worst value in each criterion among the initial solutions, which is inconsistent with Eq. (20). All HVr-based comparisons in Tables 6–11 and Figures 4 and 6 depend on this quantity, so the definition must be made precise, with a clear statement of how HV_LB is computed and why the resulting ratio measures what the paper claims.","section":"Eq. (20), §5.2"},{"comment":"The lower bound LBTC is asserted without proof. The phrase 'with Σ_{j∈P1} p_j/4 is a penalty to be added according to Webster formula' is not a justification, and no reference to a 'Webster formula' is provided. The construction is in fact valid: for any feasible original schedule, scheduling each split mono-processor task's two halves contiguously yields a feasible relaxed schedule whose weighted objective equals ΣC_j − Σ_{j∈P1} p_j/4 on processor P1 (and analogously on P2), so adding the penalty over the mono-processor tasks gives a lower bound on the original total completion time. This argument should be written out explicitly in the paper, along with a clarification that the penalty applies only to mono-processor tasks and not to the bi-processor sub-tasks. As it stands, the validity of LBTC, and hence all TC/LBTC ratios in Tables 6–11, is not established in the manuscript itself.","section":"§3.4"}],"minor_comments":[{"comment":"The text reads '0, 300 seconds' where '0.300' is clearly intended; the comma should be a decimal point.","section":"§5.1, Table 5"},{"comment":"The sentence 'For the problem of Type 2 with (α = 1.5, α = 1), Type 3 with (α = 1.5, α = 1) and Type 4 with (α = 1.5, α = 1)' is garbled; it appears that separate α values are meant for each problem type, and the repeated pairs should be corrected.","section":"§5.2, discussion of Tables 6–8"},{"comment":"Several references contain typographical errors, for example [10] 'Naval Researech Logistics' should be 'Naval Research Logistics', and [15] is titled 'Some New Uniform Design' but appears to be an Emmons scheduling paper; these should be checked and corrected.","section":"References"},{"comment":"The text says the aggregative method 'consists in generating weights for each sequence', but the uniform-design weights are generated once independently of the sequences; the wording should be clarified to avoid implying per-individual weight generation.","section":"§4.2"}],"recommendation":"major_revision","confidential_remarks":"The main claim of the paper is the 'effectiveness' of the proposed algorithms, but the evidence consists entirely of ratios to lower bounds whose tightness is unverified. The relative ranking of the three algorithms is credible because all use the same bounds, so the paper has a solid core that can be repaired. The stress-test concern about LBTC being invalid does not land: the construction is a valid relaxation, but the missing proof should be added. The hypervolume-ratio definition is the most serious technical gap and must be fixed before the quantitative comparisons can be interpreted. If the authors add exact validation on a subset of instances and clarify Eq. (20), the revised paper could be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe genuinely new piece here is the tri-objective problem P2|fixj,rj|Cmax,ΣTj,ΣCj, obtained by adding total completion time to the authors' earlier bi-objective work. That formulation is new, and so is the lower bound LBTC. The reader's worry about LBTC doesn't survive contact with the construction: splitting each mono-processor job into two half-jobs of length pj/2 and later adding pj/4 per original mono-job is a valid relaxation. In any feasible original schedule you can schedule the two halves contiguously, and the weighted objective of the relaxed schedule sits exactly pj/4 below the original ΣC for that job, so the penalty restores the original objective. It is a genuine lower bound. The presentation gap is that the text asserts it in two lines instead of proving it; that's a fixable defect, not a correctness flaw.\n\nWhat the paper does well: the problem is described cleanly, the three genetic variants (aggregative, Pareto, NSGA-II) are standard but correctly adapted, and the test bed across five instance types and three α levels is reasonable. Makespan ratios are close to the lower bound, which suggests the bound is informative and the algorithms are decent on that criterion. The relative ranking among algorithms is not circular—it is based on the same instances and direct comparisons.\n\nThe soft spots are real. First, the 'effectiveness' claim is underdetermined. Every quality number is a ratio to a lower bound of unknown tightness, and total tardiness ratios reach 99.9. If LBTT is tight, the algorithms simply fail on tardiness; if LBTT is loose, the ratio tells you nothing. No exact MIP baseline is provided even though n=10 and 20 are small enough for exact solving. Second, the hypervolume ratio in Eq. (20) is not properly defined: HVLB is never specified, and the text says the reference point comes from initial solutions rather than a lower bound. As written, HVr is not reproducible. Third, the experimental section omits basic details: population size, crossover and mutation rates, number of runs per instance, variance. Ten instances per group with averages and no spread cannot support the fine-grained comparisons in Tables 6–11.\n\nCitation pattern: the authors lean heavily on their own prior papers, but that is acceptable—LBTT comes from earlier work and is correctly credited. No sign of fabricated data.\n\nVerdict: the paper deserves a serious referee but needs major revision. The new problem is legitimate, LBTC is valid, and the heuristics are plausible. A good referee should push for a proof of LBTC, a spelled-out HVr, an exact baseline for small n, and a rewrite of the abstract that doesn't claim uniform 'effectiveness' across all three criteria.","headline":"Genuinely new tri-objective problem and a valid (if unproved) LBTC lower bound, but the 'effectiveness' claim is underdetermined by ratios to lower bounds of unknown tightness, especially for tardiness.","tokens_in":18870,"tokens_out":4353,"would_cite":false,"duration_ms":42978,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B35","68M20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Three genetic-algorithm variants (aggregative, Pareto, and NSGA-II) produce approximate Pareto fronts for the NP-hard problem of scheduling dedicated two-processor tasks under release dates, with lower bounds for makespan, total…","keywords":["scheduling","dedicated processors","multi-objective optimization","genetic algorithm","NSGA-II","Pareto front","lower bounds","total completion time"],"falsifier":"Take a small instance (say five tasks with release dates), compute the paper's $\\mathrm{LB}_{\\mathrm{TC}}$ by hand, and compare it with the exact optimal total completion time from exhaustive enumeration. Any instance where $\\mathrm{LB}_{\\mathrm{TC}}$ exceeds the true optimum refutes the claimed bound and invalidates the $TC/\\mathrm{LB}_{\\mathrm{TC}}$ quality ratios.","tokens_in":17800,"feed_emoji":"🧬","tokens_out":12722,"duration_ms":114917,"temperature":0.7,"pith_summary":"Every task in this scheduling problem is tied to one of two dedicated processors, or to both at once, and all tasks have release dates. The paper studies the simultaneous minimization of makespan, total tardiness, and total completion time, an NP-hard problem, and proposes three genetic-algorithm solvers: an aggregative version with Uniform Design weights, a Pareto-based version, and NSGA-II. To judge the quality of the approximations, the authors construct a lower bound for each criterion, including a new bound $\\mathrm{LB}_{\\mathrm{TC}}$ for total completion time obtained by splitting tasks and applying the shortest-remaining-processing-time (SRPT) theorem to underestimate completion times. The central claim, supported by experiments on instances with 10 and 20 tasks, is that the algorithms are effective: makespan and total completion time frequently land close to their lower bounds, while total tardiness remains the hardest criterion. If that claim holds, these are fast, practical solvers for a problem that arises in computer control and production systems.","feed_headline":"Genetic algorithm trio lands close to two-processor lower bounds","feed_subtitle":"A proposed completion-time bound gives the quality floor; makespan ratios stay within a few percent.","key_machinery":"The load-bearing object is a single permutation-coded genetic algorithm whose selection pressure can be switched among three mechanisms. The aggregative mechanism draws weight vectors from a Uniform Design matrix, giving seven fitness functions that are weighted sums of the three normalized criteria. The Pareto mechanism keeps all non-dominated solutions in the population and fills the rest with the best individuals for each criterion. The NSGA-II mechanism merges parents and children, sorts into non-dominated fronts, and breaks ties by crowding distance. Alongside these, the paper installs three quality floors: $\\mathrm{LB}_C$ from the two single-processor relaxations; $\\mathrm{LB}_{\\mathrm{TC}}$, built by splitting both kinds of tasks into half-length pieces, re-weighting them by $1/2$, adding the penalty $\\sum_j p_j/4$ on each processor, and applying the SRPT-based theorem [10] to underestimate completion times; and $\\mathrm{LB}_{\\mathrm{TT}}$, built from the same splitting plus an assignment step solved by the Hungarian algorithm. The lower bounds do the work of turning the heuristic fronts into measurable claims about proximity to optimality.","core_discovery":"The paper's central assertion is that the tri-objective problem $P2|fixj,rj|C_{\\max},\\sum T_j,\\sum C_j$ can be tackled effectively by adapting genetic algorithms, and that the quality of the solutions can be certified by criterion-specific lower bounds. For makespan, the bound $\\mathrm{LB}_C$ comes from relaxing the problem into two single-processor sub-problems and taking the maximum of their optimal values. For total completion time, the paper proposes $\\mathrm{LB}_{\\mathrm{TC}} = \\mathrm{Lb}_1 + \\mathrm{Lb}_2$: bi-processor tasks are split into two mono-processor subtasks, mono-processor tasks are halved with shifted release dates, a penalty $\\sum_j p_j/4$ is added on each processor, and the SRPT theorem supplies per-task completion-time underestimates. On the five instance types tested, the reported ratios $C/\\mathrm{LB}_C$ are between about $1.03$ and $1.36$, the ratios $TC/\\mathrm{LB}_{\\mathrm{TC}}$ mostly between about $1.1$ and $2.2$, and $TT/\\mathrm{LB}_{\\mathrm{TT}}$ varies much more, especially when release dates are spread widely. The conclusion the paper draws is that the three methods are effective and complementary: each one leads on at least one criterion or instance type, and the fronts are diverse enough to be useful.","pith_inferences":["A natural test not run in the paper is varying the split weight $w$ in $\\mathrm{LB}_{\\mathrm{TC}}$; the authors fix $w=1/2$, and checking whether other weights strengthen the bound would show whether that choice is essential.","The same splitting idea could be extended to more than two dedicated processors, but the penalty argument would need a new proof, since the two-processor split and the added penalty term do not transfer automatically.","Because the reported values are averages over ten random instances, reporting the spread across those instances would sharpen the effectiveness claim, a step the paper leaves implicit.","The three selection mechanisms could be transferred to other multi-objective scheduling problems with fixed job-to-machine assignments, such as the parallel-machine case the conclusion names as future work."],"forward_implications":["For instances in the tested range ($n=10$ and $n=20$, five load-balance types), the algorithms produce useful approximate Pareto fronts in under a third of a second, so the approach is fast enough for interactive or repeated use.","The total-completion-time lower bound $\\mathrm{LB}_{\\mathrm{TC}}$ gives future heuristics a concrete quality floor: any heuristic can be reported as a ratio $TC/\\mathrm{LB}_{\\mathrm{TC}}$, and a ratio near 1 indicates a schedule near the bound.","No single selection mechanism dominates: the results imply that the right choice among aggregative, Pareto, and NSGA-II depends on the objective being prioritized and on the task-load distribution.","Total tardiness is the criterion with the largest gap to its bound, especially at wide release-date spreads, identifying the place where better algorithms or tighter bounds would pay off.","The hypervolume ratio and the number of non-dominated solutions give a concrete way to rank the three methods on each instance group."],"supporting_citations":[{"why":"Supplies the makespan lower-bound relaxation into two single-processor sub-problems and the five instance-generation types used in the experiments.","marker":"[33]"},{"why":"States and proves the SRPT completion-time underestimation theorem that both LBTC and LBTT rely on.","marker":"[10]"},{"why":"Provides the tardiness lower-bound strategy (split, underestimate completion times, assign due dates) that LBTT adapts.","marker":"[24]"},{"why":"Gives the Uniform Design method that generates the seven weight vectors for the aggregative genetic algorithm.","marker":"[32]"},{"why":"Defines the NSGA-II procedure (non-dominated sorting, crowding distance, elitism) that one proposed variant implements.","marker":"[13]"},{"why":"Introduces the hypervolume indicator used to compare the quality of the Pareto fronts.","marker":"[9]"},{"why":"Supplies the software used to compute the hypervolume values in the numerical section.","marker":"[17]"},{"why":"Contributes the assignment-based technique, solved with the Hungarian algorithm, used in the tardiness lower bound.","marker":"[37]"}],"fun_headline_variants":["GA trio near two-processor scheduling bounds","Multi-objective scheduling conquered by three GAs","Lower bounds certify genetic algorithm schedules","Two-processor scheduling: GAs hit near bounds","Three genetic algorithms tackle multi-objective scheduling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the split-and-penalty relaxation, including the added term $\\sum_j p_j/4$, gives a value at or below the true optimal total completion time; if that inequality ever fails, the $TC/\\mathrm{LB}_{\\mathrm{TC}}$ columns in the result tables are not valid quality measures.","fun_headline_variants_meta":{"raw":{"variants":["GA trio near two-processor scheduling bounds","Multi-objective scheduling conquered by three GAs","Lower bounds certify genetic algorithm schedules","Two-processor scheduling: GAs hit near bounds","Three genetic algorithms tackle multi-objective scheduling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000428,"raw_usage":{"total_tokens":2213,"prompt_tokens":993,"completion_tokens":1220,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":609,"completion_tokens_details":{"reasoning_tokens":1153}},"tokens_in":609,"tokens_out":1220,"duration_ms":8712,"temperature":1.0,"reasoning_tokens":1153,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:42:08.127934+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small instance (say five tasks with release dates), compute the paper's $\\mathrm{LB}_{\\mathrm{TC}}$ by hand, and compare it with the exact optimal total completion time from exhaustive enumeration. Any instance where $\\mathrm{LB}_{\\mathrm{TC}}$ exceeds the true optimum refutes the claimed bound and invalidates the $TC/\\mathrm{LB}_{\\mathrm{TC}}$ quality ratios.","supporting_citations":[{"cited_title":"and Chu, C","cited_arxiv_id":null,"evidence_quote":"Supplies the makespan lower-bound relaxation into two single-processor sub-problems and the five instance-generation types used in the experiments."},{"cited_title":"Scheduling multiprocessor tasks on two parallel processors.A branch and bound algorithm to minimize the total of tardness with different release date","cited_arxiv_id":null,"evidence_quote":"States and proves the SRPT completion-time underestimation theorem that both LBTC and LBTT rely on."},{"cited_title":"and Dammak, A","cited_arxiv_id":null,"evidence_quote":"Provides the tardiness lower-bound strategy (split, underestimate completion times, assign due dates) that LBTT adapts."},{"cited_title":"and Wang, Y","cited_arxiv_id":null,"evidence_quote":"Gives the Uniform Design method that generates the seven weight vectors for the aggregative genetic algorithm."},{"cited_title":"and Meyarivan, T","cited_arxiv_id":null,"evidence_quote":"Defines the NSGA-II procedure (non-dominated sorting, crowding distance, elitism) that one proposed variant implements."},{"cited_title":"The hypervolume indicator for multi-objective optimisation: Calculation and use","cited_arxiv_id":null,"evidence_quote":"Introduces the hypervolume indicator used to compare the quality of the Pareto fronts."},{"cited_title":"and Guerreiro, A.P","cited_arxiv_id":null,"evidence_quote":"Supplies the software used to compute the hypervolume values in the numerical section."},{"cited_title":"and Adjallah, K","cited_arxiv_id":null,"evidence_quote":"Contributes the assignment-based technique, solved with the Hungarian algorithm, used in the tardiness lower bound."}],"review_version":1}