{"id":"e56c4c8d-0da9-4f5e-9339-c13d200dc380","arxiv_id":"2507.08725","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"With fixed task mapping and ordering, minimizing carbon cost by shifting task start times is polynomial for one processor, NP-hard for multiple, and a new greedy+local-search framework approaches the ILP optimum.","lead":"Researchers formalize the problem of shifting workflow tasks in time to cut carbon emissions, given fixed task placement, and show it is easy on one processor but hard on many. They provide a heuristic scheduler, CaWoSched, that cuts carbon cost to about 60% of the standard deadline-aware schedule in simulations, plus an ILP for small instances.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The DP in Theorem 4.1 drops idle power from the objective, so Eq. (1) can return a suboptimal one-processor schedule under the paper's own cost model.","rationale":"The reader's weakest_assumption (forecast uncertainty in G_j) is a legitimate modeling limitation, but it is not an internal correctness risk. The DP issue is more load-bearing: Theorem 4.1 is the paper's main positive complexity result, and the recurrence as written does not minimize the objective defined in Section 3. A concrete one-task instance shows a strict preference for the wrong start time. The NP-hardness reduction sets P_idle=0, so Theorem 4.3 is unaffected; the experimental setup also ensures green power covers idle power, so the empirical conclusions are not directly invalidated. Because the fix is simple (include the idle-gap cost in each transition, preserving polynomiality), the right disposition remains conditional rather than reject. The E-schedule lemma and its proof need the same correction because shifting a block also shifts idle time in the opposite direction. Thus the paper is promising but its central polynomial algorithm must be revised.","tokens_in":19006,"tokens_out":27882,"duration_ms":343082,"concrete_test":"Implement Eq. (1) exactly as written for the single-task instance above (P_idle=2, P_work=2, T=6, G=(3,3,3,0,5,5), omega=3) and compare with brute-force enumeration of both start times using the full Section 3 cost. If the DP returns start 0 with cost 3 instead of start 3 with cost 4, the recurrence is not computing Opt(i,t). Then rerun with an explicit idle-gap cost added to the transition; recovering start 3 would show the theorem is repairable but the published algorithm and proof need amendment.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 3 defines total carbon cost over [0,T) as sum_t max(P_t - G_j,0), with every processor consuming P_idle even while idle. The DP of Theorem 4.1 charges only cc(vi,t), the execution cost of vi on [t-omega(vi),t), and never charges idle intervals between the previous completion s and the start of vi, or after the last task. Since max(P_idle - G_j,0) varies across intervals, this is not a constant offset. Counterexample: P_idle=2, P_work=2, T=6, one task of length 3, and G=(3,3,3,0,5,5). Starting at 0 gives active cost 3 plus idle cost 2, total 5; starting at 3 gives idle cost 0 plus active cost 4, total 4. The true optimum starts at 3, but Eq. (1) compares only active costs (3 vs. 4) and returns start 0. The same omission underlies Lemma 4.2, whose block-shift argument moves load but not the counter-moving idle power. The polynomial-time claim is therefore not established by the published recurrence; a corrected DP would add an idle-gap term to each transition.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies carbon-aware workflow scheduling with a fixed mapping and ordering of tasks on a heterogeneous cluster, where each processor has idle and work power, and the green energy budget varies over time. The total carbon cost is the time-integrated excess of total power over the green budget. The authors claim a polynomial-time dynamic program for the single-processor case, strong NP-completeness for the multiprocessor case, an ILP formulation, and a family of heuristics (CaWoSched) with experimental evaluation against an ASAP baseline and exact solutions on small instances. The theoretical claims are central to the paper: the uniprocessor polynomial-time result rests on a dynamic program (Theorem 4.1) and an E-schedule structural lemma (Lemma 4.2), and the multiprocessor hardness claim is Theorem 4.3.","tokens_in":19260,"tokens_out":8555,"duration_ms":92165,"significance":"If the theoretical claims were correct, the paper would provide a clean complexity dichotomy for a natural scheduling problem and a practical heuristic framework with strong experimental support. The paper's strengths include a rigorous 3-Partition reduction (for a variable number of processors), a correct time-indexed ILP that includes idle power, and an extensive, reproducible experimental study with public code and data. However, the central uniprocessor polynomial-time result is not established under the paper's own cost model because the dynamic program omits idle-power costs, and the hardness claim as stated for 'at least two processors' is stronger than what the reduction actually proves. These issues are load-bearing and require substantial revision.","major_comments":[{"comment":"The dynamic programming recurrence Opt(i,t) = min_{s ≤ t-ω(vi)} {Opt(i-1,s) + cc(vi,t)} charges only cc(vi,t), the cost of executing task vi during [t-ω(vi), t[, and never charges the idle intervals between the end of vi-1 and the start of vi, nor idle time after the last task. Under the cost model of Section 3 (CC_t = max(P_t - G_j, 0) with P_t = sum_i P_i(t), including idle power), this omitted idle cost is not a constant offset because G_j varies across intervals. For example, take P_idle = 2, P_work = 2, T = 6, one task of length 3, and G = (3,3,3,0,5,5). The true optimal schedule starts at time 3 with total cost 4 (idle cost 0, active cost 4), while the DP comparing only active costs returns start time 0 (active cost 3, true total cost 5). Thus Theorem 4.1 is not established by the published recurrence.","section":"Section 4.1, Eq. (1)"},{"comment":"The proof of Lemma 4.2 claims that shifting a block of tasks to an interval with a higher green power budget 'cannot have increased' the carbon cost. This argument moves only the active load and ignores the idle power that moves in the opposite direction. Since idle power contributes to P_t and the green budget varies, the net change in cost includes a term for the idle intervals vacated and occupied by the shift. The proof therefore does not establish the existence of an optimal E-schedule under the paper's cost model. This undermines the restriction to the polynomial-size set E' that is used to make the DP polynomial-time.","section":"Appendix A.2, Lemma 4.2"},{"comment":"The 3-Partition reduction constructs an instance with P = 3n processors, one processor per task. This proves strong NP-completeness for the class of instances where the number of processors is part of the input, but it does not prove NP-hardness for any fixed number of processors P ≥ 2, such as P=2. The abstract and introduction claim the problem is NP-hard 'for at least two processors,' which is a stronger statement than the reduction supports. Please either revise the claim to 'when the number of processors is part of the input' or provide a separate reduction for fixed P ≥ 2.","section":"Section 4.2, Theorem 4.3"}],"minor_comments":[{"comment":"The caption says 'cost ratios obtained by dividing heuristics carbon cost by the carbon cost of the deadline'; this should read 'by the carbon cost of the baseline' (or similar), since the text describes a comparison against the ASAP baseline.","section":"Figure 4 caption"},{"comment":"The description of the block subdivision says every task starts at the beginning of an interval 'when we look at the special case of one processor.' This is motivated by Lemma 4.2, but since Lemma 4.2 is not established under the full cost model (see major comment 2), the heuristic's design rationale should be reworded or supported independently.","section":"Section 5.2"},{"comment":"The power values for communication links are drawn randomly between 1 and 2, but the exact seed or distribution is not specified; the paper states the data are available, so this is a minor reproducibility note.","section":"Section 6.1"}],"recommendation":"major_revision","confidential_remarks":"The paper has two load-bearing technical issues: the uniprocessor DP omits idle power and the P=2 hardness claim is not supported by the reduction. The NP-hardness reduction for variable P is sound, and the experimental work is substantial and reproducible. The authors should be given the opportunity to fix the DP (e.g., by adding idle-gap terms and proving a suitable structural lemma) and to correct the hardness claim. The stress-test concern about idle power is real and lands directly on the paper's central theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe multiprocessor NP-hardness proof and the heuristic study are the real value here; the uniprocessor DP is not. Theorem 4.1 claims polynomial time, but recurrence (1) charges only the active cost cc(vi,t) and never accounts for idle power of the processor between tasks, or before the first and after the last task. In the paper's own cost model, max(P_idle - G_j, 0) varies over intervals, so this is not a constant offset. The stress-test counterexample is correct: P_idle=2, P_work=2, one task of length 3, T=6, G=(3,3,3,0,5,5). Starting at 0 gives total cost 5 (active 3 + idle 2); starting at 3 gives total cost 4 (active 4 + idle 0). The recurrence picks start 0. The same gap invalidates Lemma 4.2's block-shift argument, which moves load but ignores the idle power left behind. So the central theoretical claim is not established.\n\nWhat is good: the problem formulation (fixed mapping/order, time-varying green budgets, deadline) is new relative to the literature. The strong NP-completeness reduction from 3-Partition (Theorem 4.3) is clean and correct, with a nice use of zero-idle power to make the bound meaningful. The ILP in Section 4.3 is correct and does include idle power. The CaWoSched framework is well-engineered, with public code and data, and the comparison against the ILP on small instances gives an honest sanity check.\n\nOther soft spots are minor: 'fully polynomial' is used loosely; the experimental baseline is only ASAP, which is a weak competitor, so the ~0.6x median ratio should be read as 'better than ASAP' rather than 'good in absolute terms'; and the k and mu parameters are hand-tuned without sensitivity analysis.\n\nWho is this for: researchers in green/sustainable computing who want the first complexity results for carbon-aware scheduling with a fixed mapping, plus a practical scheduler. The NP-hardness and the heuristics deserve a serious referee, even though the DP needs major repair.\n\nRecommendation: send to peer review, but ask for a major revision. The authors should fix the DP (a corrected recurrence that includes idle gap costs is likely possible), or explicitly restrict the model to zero idle power for the polynomial-time claim. The paper should not be desk-rejected.","headline":"Solid NP-hardness and heuristic contributions, but the single-processor DP drops idle power and its polynomial-time claim is not established.","tokens_in":19811,"tokens_out":5010,"would_cite":false,"duration_ms":52997,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M20","68Q17","90B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes a complexity dichotomy: carbon-aware scheduling with a fixed task mapping is polynomial on one processor and strongly NP-complete on two or more processors, and its greedy-plus-local-search heuristics cut median…","keywords":["carbon-aware scheduling","workflow scheduling","fixed mapping","deadline constraint","dynamic programming","NP-completeness","greedy heuristics","green energy"],"falsifier":"Take a known unsolvable 3-Partition instance, build the multi-processor reduction instance from Theorem 4.3, and ask an exact ILP whether a zero-carbon schedule exists; a 'yes' answer would refute the strong NP-completeness proof. Alternatively, run CaWoSched with realized green budgets that differ from the forecast budgets and check whether its carbon cost stays below ASAP's; a case where it exceeds ASAP would show the exact-budget assumption is load-bearing.","tokens_in":18791,"feed_emoji":"⚡","tokens_out":6434,"duration_ms":71433,"temperature":0.7,"pith_summary":"This paper tries to establish exactly how hard it is to cut a workflow's carbon emissions by shifting task execution into greener time intervals when the task-to-processor mapping and the order on each processor are already fixed. It proves that the single-processor version of this problem is solvable in polynomial time, while the version with two or more processors is strongly NP-complete even for independent tasks on identical processors. It then offers CaWoSched, a family of 16 greedy-plus-local-search heuristics, and reports that they cut median carbon cost to roughly 0.58–0.6 of the ASAP baseline, with near-optimal performance on small instances. If the complexity results hold, they tell practitioners which settings need exact methods and which can be left to heuristics.","feed_headline":"Carbon-aware scheduling: easy on one CPU, NP-hard on two","feed_subtitle":"New heuristics hit about 60 percent of baseline carbon cost and match optimal on small workflows.","key_machinery":"The argument is carried by the communication-enhanced DAG $G_c$, which replaces every inter-processor communication with a fictional task on a fictional link-processor, so that all scheduling decisions reduce to placing tasks on a timeline. The polynomial result uses the notion of an E-schedule: a single-processor schedule in which every block of consecutive tasks starts or ends at an interval boundary; Lemma 4.2 shows an optimal E-schedule always exists, which restricts the dynamic program's candidate end times to $O(n^3J)$ values. For the heuristics, the load-bearing mechanisms are the task scores (slack $s(v)$, pressure $\\rho(v)=\\omega(v)/(s(v)+\\omega(v))$, and their power-weighted variants), the refinement of intervals into subintervals induced by blocks of up to $k=3$ tasks, and a local-search hill climber that moves tasks within $[\\mathrm{EST}(v), \\mathrm{LST}(v)]$.","core_discovery":"On the paper's own terms, the central discovery is a complexity dichotomy: with one processor and a fixed task order, an optimal carbon-minimizing schedule can be computed in polynomial time via a dynamic program that only needs to consider task end times aligned with interval boundaries (E-schedules); with at least two processors, the problem is strongly NP-complete, so no polynomial exact algorithm exists unless P=NP. In the hard regime, the paper's CaWoSched framework combines slack- and pressure-based greedy scores, refined interval subdivisions, and local search to produce schedules whose carbon cost is close to the best known and, on small workflows, close to the ILP optimum.","pith_inferences":["Editorial inference: because mapping and ordering are taken as given, the reported savings are relative to a mapping chosen without carbon in mind; a carbon-aware mapping pass could push savings beyond the 0.58–0.6 ratio.","Editorial inference: the E-schedule lemma exploits exact interval boundaries, so extending the one-processor result to uncertain green budgets would likely require a stochastic or robust reformulation rather than a direct adaptation of the dynamic program.","Editorial inference: the local-search refinement accounts for a large share of the carbon improvement, so a cheaper stand-alone hill climber starting from an ASAP schedule might capture most of the benefit on very large DAGs."],"forward_implications":["On a single processor, carbon-aware scheduling with a fixed order is tractable, so exact schedules can replace heuristics in that setting.","On clusters with two or more processors, the problem is strongly NP-complete, which justifies heuristic approaches and rules out a general polynomial exact algorithm.","CaWoSched's median carbon cost is about 0.58–0.6 times the ASAP baseline, roughly a 40 percent reduction, and the saving grows when the deadline is looser.","Several heuristic variants match the ILP-optimal cost on a meaningful share of small instances while running orders of magnitude faster than the exact solver.","Running times stay in seconds for most workflows and a few minutes for the largest tested workflows (up to 30,000 tasks), making the approach usable in planning tools."],"supporting_citations":[{"why":"HEFT provides the standard mapping and ordering that the fixed-mapping setting takes as given.","marker":"[34]"},{"why":"Documents the carbon savings available from shifting execution times to greener intervals, motivating the problem.","marker":"[38]"},{"why":"Supplies the NP-completeness framework and the 3-Partition problem used in the hardness reduction.","marker":"[15]"},{"why":"Provides the real-world workflow DAGs and processor power parameters used in the experiments.","marker":"[6]"},{"why":"WFGen generates the scaled simulated workflow instances.","marker":"[11]"},{"why":"The ILP solver used to compute optimal solutions for small instances.","marker":"[16]"},{"why":"Kahn's topological-sort algorithm underlies the EST/LST computations in the baseline and greedy methods.","marker":"[21]"}],"fun_headline_variants":["Carbon-aware scheduling: easy on one CPU, NP-hard on many","One CPU simple, many CPUs hard: carbon-aware scheduling","Cluster scheduling for low carbon: NP-hard, so use heuristics","Carbon-aware workflow scheduling: P vs NP depends on CPU count"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"That the green power budget in every time interval is known exactly and stays constant within the interval; if the forecast is wrong, the shifted schedule may no longer be better than ASAP, and the complexity results do not cover stochastic budgets.","fun_headline_variants_meta":{"raw":{"variants":["Carbon-aware scheduling: easy on one CPU, NP-hard on many","One CPU simple, many CPUs hard: carbon-aware scheduling","Cluster scheduling for low carbon: NP-hard, so use heuristics","Carbon-aware workflow scheduling: P vs NP depends on CPU count"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001131,"raw_usage":{"total_tokens":4657,"prompt_tokens":857,"completion_tokens":3800,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":3728}},"tokens_in":473,"tokens_out":3800,"duration_ms":31164,"temperature":1.0,"reasoning_tokens":3728,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:11:49.897548+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a known unsolvable 3-Partition instance, build the multi-processor reduction instance from Theorem 4.3, and ask an exact ILP whether a zero-carbon schedule exists; a 'yes' answer would refute the strong NP-completeness proof. Alternatively, run CaWoSched with realized green budgets that differ from the forecast budgets and check whether its carbon cost stays below ASAP's; a case where it exceeds ASAP would show the exact-budget assumption is load-bearing.","supporting_citations":[{"cited_title":"Topcuoglu, S","cited_arxiv_id":null,"evidence_quote":"HEFT provides the standard mapping and ordering that the fixed-mapping setting takes as given."},{"cited_title":"Wiesner, I","cited_arxiv_id":null,"evidence_quote":"Documents the carbon savings available from shifting execution times to greener intervals, motivating the problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the NP-completeness framework and the 3-Partition problem used in the hardness reduction."},{"cited_title":"Bader, F","cited_arxiv_id":null,"evidence_quote":"Provides the real-world workflow DAGs and processor power parameters used in the experiments."},{"cited_title":"Coleman, H","cited_arxiv_id":null,"evidence_quote":"WFGen generates the scaled simulated workflow instances."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Kahn's topological-sort algorithm underlies the EST/LST computations in the baseline and greedy methods."}],"review_version":1}