{"id":"6f2b112e-9bb1-4488-bfb5-b9d0b140c515","arxiv_id":"2501.14765","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A hybrid cooperative co-evolution algorithm with a Petri-net-based deadlock amendment method is proposed for distributed assembly flowshop scheduling with limited buffers.","lead":"This paper presents a scheduling algorithm for factories that produce parts and then assemble them into products, when the assembly buffer has limited space and can jam. It uses a Petri net model and a Banker's-algorithm-like repair method to prevent jams, and a hybrid evolutionary algorithm to find faster schedules.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Backward makespan equations (Section III.D) can compute infeasible schedules, so IDAM's abstract deadlock-freeness is not shown to translate to real DAFSP; reported makespans may be invalid.","rationale":"The reader's weakest_assumption identified the gap between the untimed APP and the timed DAFSP; this review sharpens that gap into a concrete failure of the makespan equations. The example shows the backward construction can produce completion times that violate the very flowshop capacity constraints the problem definition assumes, so the computed CAmax is not a feasible makespan. Because the experimental section compares algorithms only through this CAmax, the central 'outperforms on all instances' claim is not trustworthy as presented. Secondary concerns, such as unreported adaptation of baseline algorithms and in-sample parameter calibration, reinforce the need for revision but are not the load-bearing issue. The paper does have a plausible core idea, using Petri nets plus a Banker's-style check to repair orderings, and IDAM's polynomial-time claim is plausible if IBA is treated as a subroutine, but the feasibility guarantee is precisely where the argument fails. A revised version that replaces Eq. (3) with a correct forward or backward scheduling procedure that provably respects both factory capacity and the IDAM-safe order, and that re-runs all experiments, could change the verdict.","tokens_in":26792,"tokens_out":15849,"duration_ms":153717,"concrete_test":"Implement the schedule implied by Eqs. (2)-(9) and forward-simulate it for the 4-job counterexample (f=2, m=1, AP1={i1,i2}, AP2={i3,i4}, Psi=2, lambda'=(i1,i2,i3,i4), mu=(F1,F2,F1,F2), p_i3=p_i4=5, other p=1). Check whether i1 and i3 overlap on F1's machine or i2 and i4 overlap on F2's machine; if overlap occurs, the backward makespan calculation is invalid. For broader confirmation, run the same forward-feasibility check on all 324 instances and report the fraction of reported best schedules that violate machine-capacity or buffer-release constraints.","verdict_should_be":"REJECT","load_bearing_attack":"IDAM operates only on the APP model, whose initial marking in Definition 1 Step 3 sets M0(pi)=1 for every job, i.e., all jobs are simultaneously finished and ready to enter the assembly buffer. Deadlock-freeness in this untimed Petri net means only that some buffer-entry order exists; it says nothing about whether the amended order lambda' can be realized when jobs complete at different times in the factories and may block the last machine when BA is full. Section III.D attempts to force realization by assigning last-machine completion times through Eq. (3): consecutive jobs in lambda' assigned to the same factory get C_h=S_{h+1}, otherwise C_h=C_{h+1}-1. This does not enforce within-factory capacity constraints when jobs from the same factory are separated in lambda' by jobs from other factories. Concretely, with f=2, m=1, u=4, products AP1={i1,i2}, AP2={i3,i4}, Psi=2, lambda'=(i1,i2,i3,i4), mu=(F1,F2,F1,F2), the sequence is IDAM-safe. Eq. (3) yields C_i1=C_i4-3, C_i2=C_i4-2, C_i3=C_i4-1. Feasibility on F1's single machine requires C_i1 <= C_i3-p_i3, i.e. p_i3<=2; feasibility on F2 requires C_i2 <= C_i4-p_i4, i.e. p_i4<=2. For p_i3=p_i4=5, no feasible schedule exists with these completion times, yet the equations output a makespan. Thus CAmax can correspond to no realizable DAFSP schedule, and the claim that IDAM ensures feasible deadlock-free solutions in the timed problem is unsupported. All comparisons in Section V use this makespan calculation, so the reported superiority of HCCE rests on potentially invalid schedules.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a hybrid cooperative co-evolution (HCCE) algorithm for the distributed assembly flowshop scheduling problem (DAFSP) with limited assembly buffers, aiming to minimize makespan while avoiding deadlocks. The authors model the buffer-entry process with an assembly procedure Petri net (APP), propose an improved Banker's algorithm (IBA) to check the safety of a marking, and develop IDAM, a polynomial-time method that amends an arbitrary job permutation into a deadlock-free one. They then integrate IDAM into a cooperative co-evolution framework with an elite archive, problem-specific heuristics, information transfer, and four local-search operators. Computational experiments on 324 generated instances report that HCCE outperforms three state-of-the-art algorithms (HHMA, EDMBO, PBIGA) and three self-designed variants, with Friedman test p-values of 0. The paper claims, in the abstract and contributions, that IDAM guarantees feasible (deadlock-free) solutions and that the backward makespan calculation maintains this property.","tokens_in":27157,"tokens_out":7829,"duration_ms":73831,"significance":"If the central claims were correct, the paper would make a useful contribution to scheduling under limited buffers, a real concern in semiconductor and food processing systems. The idea of translating deadlock avoidance into a Petri-net/Banker's-algorithm check and embedding it into a population-based metaheuristic is interesting and, to the best of my knowledge, not previously applied to DAFSP. The algorithmic machinery is described in enough detail to be reimplemented, and the comparison against multiple baselines is welcome. However, the significance hinges on whether the deadlock-freeness guarantee actually transfers to the timed scheduling problem and whether the reported makespans correspond to realizable schedules. The paper does not supply a formal proof of that transfer, and a concrete counterexample shows that the backward makespan calculation can output infeasible schedules. Because all experimental results are computed with that makespan, the empirical claims are not trustworthy as presented.","major_comments":[{"comment":"The backward makespan calculation does not guarantee feasibility of the resulting schedule. Consider f=2, m=1, u=4, AP1={i1,i2}, AP2={i3,i4}, buffer capacity Psi=4, lambda'=(i1,i2,i3,i4), mu=(F1,F2,F1,F2). This lambda' is IDAM-safe because the buffer can hold all jobs simultaneously. Equation (3) assigns completion times C_i1=Time-3, C_i2=Time-2, C_i3=Time-1, C_i4=Time on the single machine. On F1, feasibility requires S_i3 >= C_i1, i.e., Time-1-p_i3 >= Time-3, or p_i3 <= 2. Similarly on F2, p_i4 <= 2. For p_i3=p_i4=5, no feasible single-machine schedule exists with these completion times, yet Eqs. (7)-(9) output a makespan. Thus the claim in contribution 2 that the backward method 'maintains the deadlock-freeness of solution' is unsupported; deadlock-freeness of the buffer order does not imply machine-capacity feasibility of the timed schedule. Since Section V uses this makespan as the performance metric, the reported superiority of HCCE may be based on invalid objective values.","section":"Section III.D, Eqs. (2)-(9)"},{"comment":"The APP model initializes M0(pi)=1 for every job i, i.e., all jobs are assumed to be simultaneously finished and ready to enter the assembly buffer at time zero. IDAM only certifies that a deadlock-free buffer-entry order exists under this untimed, all-jobs-ready abstraction. The paper does not prove that a sequence safe under this abstraction remains safe in the actual timed DAFSP, where jobs complete at different times and, under assumption (5), a finished job is removed into BA only if space is available; otherwise it must block the last machine of its factory. A blocking last machine can propagate and create a deadlock even when the buffer-entry order is the one produced by IDAM. No argument is given that the backward schedule of Section III.D prevents such blocking, and the counterexample above shows that the backward equations can violate machine availability. Consequently, the abstract's claim that IDAM 'ensure[s] the feasibility (i.e., deadlock-freeness) of solutions' is not established for the real problem.","section":"Section III.C.1, Definition 1 (Step 3) and Remark 1"},{"comment":"The paper states that IDAM has complexity O(u^2), but this ignores the cost of each IBA call in Algorithm 1. IBA itself contains a loop over unfinished products (lines 4-18), and each iteration scans products to build the set Psi, so a single IBA call costs at least O(l^2) in the worst case, where l is the number of products. The total complexity of IDAM is therefore O(u^2 * l^2) (or O(u^2 * l) with a careful implementation), not O(u^2) as claimed in the abstract and in Section III.C.3. Polynomial complexity remains, but the stated bound is inaccurate and should be corrected.","section":"Section III.C.3, 'Computational complexity of Algorithm IDAM'"}],"minor_comments":[{"comment":"The parameter calibration is performed on instances from the same distribution as the test set (e.g., medium calibration uses u x f x m x l = 40 x 4 x 10 x 8, which also appears as a test size). The reported superiority of HCCE is therefore based on parameters tuned to the test distribution; the paper should explicitly discuss this potential source of overfitting to the benchmark.","section":"Section V.B, Table V vs. Section V.A"},{"comment":"The symbol 'Time' is used for two different purposes: as a variable in Eq. (2) denoting the completion time of the last job on the last machine, and as a multiplier in the termination criterion 'Time x u x f x m x l ms' in Section V.A. Please use distinct notation to avoid confusion.","section":"Eq. (2) and Section V.A"},{"comment":"The Friedman test results report Chi-Square and P-value but do not state the number of algorithms k, the number of instance groups N, or the degrees of freedom. These details are needed for the reader to verify the statistical analysis. Also, 'Freidman' should be spelled 'Friedman'.","section":"Tables VII and IX"},{"comment":"Reference [10] (Cao et al.) is mentioned in the Introduction for the claim that deadlock in DASP is related to the order of finished jobs entering the buffer, but it is not discussed in the Literature Review. If that reference already addresses deadlock control for a two-stage assembly flowshop with limited buffers, the assertion 'for the first time, we use Petri nets to analyze the deadlocks in DAFSP' should be qualified by explaining what is truly new relative to [10].","section":"Section II and reference [10]"},{"comment":"The paper reports only relative percentage deviations (RPD) and not the actual CAmax values for any instance. Reporting absolute makespans (or at least the best-known values per instance) would help readers assess the practical magnitude of the improvements.","section":"Section V, Tables VI and VIII"},{"comment":"Several equations are rendered with misplaced braces, fractions, and symbols (e.g., Eq. (3) shows a garbled 'if' condition, and Eq. (8) has ambiguous indentation). The equations should be typeset cleanly so that the algorithmic intent is unambiguous.","section":"Equations (3)-(5), (8)"}],"recommendation":"reject","confidential_remarks":"The paper addresses a relevant problem and contains a substantial algorithmic design, but the central feasibility guarantee is invalidated by the counterexample in Major Comment 1. Fixing this would require either (a) proving that the backward makespan equations always yield a feasible schedule for IDAM-safe sequences (which the counterexample shows is false), or (b) replacing the makespan calculation with a forward simulation with proper blocking and deadlock detection, which would change the algorithm and the claimed contribution. Given that all experimental conclusions depend on the current makespan, the manuscript would need a fundamental revision. The paper is borderline for a scheduling journal; the novelty of the Petri-net-based deadlock amendment is interesting, but the untimed abstraction gap and the infeasible backward calculation are major correctness issues."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the important thing to know: the IDAM idea is sound as an abstraction, but the paper's makespan calculation can return numbers that do not correspond to any feasible schedule. The stress-test example is correct. With f=2, m=1, u=4, AP1={i1,i2}, AP2={i3,i4}, Psi=2, lambda'=(i1,i2,i3,i4), mu=(F1,F2,F1,F2), Eq. (3) gives C_i1 = C_i4 - 3 and C_i3 = C_i4 - 1. On F1's single machine that requires p_i3 <= 2; if p_i3 = 5, no real schedule exists, yet the equations output a makespan. The paper never proves that an IDAM-safe sequence is realizable in the timed system where jobs finish at different times and can block the last machine when the buffer is full. Since every result in Section V uses this makespan, the empirical claims are currently unsupported.\n\nWhat is genuinely new: the problem variant (DAFSP with limited buffers and deadlock) is new, and modeling buffer entry with a Petri net and applying Banker's algorithm to repair job order is a credible idea. The HCCE algorithm is assembled from known pieces, but the description is clear and the computational study is extensive: 324 instances, three variants, three baselines, Friedman tests.\n\nOther soft spots, in order: the baseline algorithms were not designed for deadlock-prone DAFSP, and the paper does not say how they were adapted. Parameter calibration uses instances from the same distribution as the test set, so the RPD comparisons are optimistic. No code or data is released. These are secondary to the makespan issue but need addressing.\n\nWho it's for: scheduling researchers working on assembly flowshops or on Petri net deadlock control. The IDAM abstraction is worth reading; the numerical results are not trustworthy yet.\n\nRecommendation: send to peer review. The problem is real, the core idea is worth developing, and the flaw is fixable in principle (compute makespan by forward simulation that respects capacity, or prove that Eqs. (3)-(9) yield feasible schedules). A referee should demand that fix, plus baseline adaptation details, out-of-sample tuning, and code/data.","headline":"A credible deadlock-avoidance idea for a real scheduling problem, but the makespan calculation can return infeasible schedules, so the experimental results are not yet trustworthy.","tokens_in":27746,"tokens_out":3351,"would_cite":false,"duration_ms":32291,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B35","68Q85"],"pacs":[],"model":"deepseek-v4-flash","headline":"A Petri net repair that amends job order in quadratic time makes limited-buffer assembly schedules deadlock-free, and embedding it in a cooperative co-evolution search lowers makespan below three prior algorithms on all tested instances.","keywords":["distributed assembly flowshop scheduling","deadlock-free scheduling","Petri nets","Banker's algorithm","cooperative co-evolution","limited buffer","makespan minimization","assembly buffer deadlock"],"falsifier":"Forward-simulate any HCCE solution on the paper's smallest instance type using the processing times generated by the benchmark; if the backward makespan equations ever yield a negative start time, or the simulated buffer ever fills with jobs whose product is not completable, then the claimed IDAM guarantee plus backward calculation does not describe a realizable deadlock-free schedule.","tokens_in":26560,"feed_emoji":"⚙️","tokens_out":8470,"duration_ms":81566,"temperature":0.7,"pith_summary":"Limited-buffer assembly lines can stall completely when the buffer fills with jobs that cannot yet be assembled because their product's remaining jobs have not arrived. This paper claims that such deadlocks are caused by the order in which finished jobs enter the assembly buffer, and that a repair procedure built on a Petri net model and a Banker's-algorithm-style safety check can always convert any job order into a deadlock-free one in O($u^{2}$) time. Embedding this repair inside a hybrid cooperative co-evolution algorithm, the paper reports lower makespan than three existing algorithms on all 324 tested instances. A sympathetic reader should take away that deadlock can be treated as a scheduling constraint at the job-order level rather than as a separate control problem.","feed_headline":"Petri net repair turns deadlock-prone assembly schedules deadlock-free","feed_subtitle":"Quadratic-time deadlock repair inside cooperative co-evolution beats three prior algorithms on all test instances.","key_machinery":"The key object is the assembly-procedure Petri net (APP), which models each job's move into the limited buffer as a transition firing and each product's assembly as another transition that returns buffer tokens. On top of it, an improved Banker's algorithm (IBA) tests whether a marking is safe, meaning some sequence of product-assembly firings can still finish all products; IDAM then walks along a candidate job permutation, firing entries one by one and moving any transition that would create an unsafe marking to the back of the order. This converts an arbitrary job permutation into a deadlock-free one. The HCCE algorithm carries two subpopulations, one of job permutations and one of factory permutations, and uses the repair inside initialization, global evolution, information transfer, and local search.","core_discovery":"The central claim is that, for a distributed assembly flowshop with a limited assembly buffer, deadlock-freeness of a schedule is equivalent to deadlock-freeness of the order in which jobs enter the buffer, and that this order can be checked and amended using an assembly-procedure Petri net together with an improved Banker's algorithm. The paper's IDAM procedure reads a candidate job permutation, fires the corresponding buffer-entry transitions, and whenever a transition would lead to a marking from which no product can ever be completed, moves that transition to the end of the sequence. The resulting permutation is deadlock-free by construction, and the whole repair costs O($u^{2}$). The paper then folds this repair into a two-subpopulation cooperative co-evolution algorithm with an elite archive, and computes the system makespan with backward equations that maintain the repaired order's feasibility. On 324 generated instances, HCCE reports lower best and average relative percentage deviations than HHMA, EDMBO, and PBIGA for small, medium, and large instance groups.","pith_inferences":["If the central claim holds, the same buffer-order repair could be tried on other two-stage systems where a batch needs several parts and a limited buffer, such as final assembly in electronics or food processing; the paper itself does not test those settings.","The paper leaves implicit that the safety certificate is checked on a zero-ready-time abstraction; a natural extension is to verify with a discrete-event simulator that an IDAM-safe order never blocks under realistic arrival times.","An extension not explored in the paper is dynamic repair: instead of repairing the whole permutation once, IDAM could be reapplied when new jobs or urgent product insertions arrive, using the remaining buffer state as the initial marking.","The backward makespan equations could be tested against forward simulation as an independent audit; this would show whether the repaired order also minimizes or merely respects the assembly constraints."],"forward_implications":["Any schedule produced through IDAM is deadlock-free by construction, so limited-buffer DAFSP solutions can be certified without building a separate deadlock controller.","Because the repair costs O(u^2), it can be run inside every fitness evaluation of a metaheuristic without changing the algorithm's asymptotic character.","The two-permutation coding separates the job-order problem from the factory-assignment problem, allowing cooperative co-evolution to search both spaces with problem-specific operators.","On the paper's 324 instances, HCCE reports lower best and average RPD than HHMA, EDMBO, and PBIGA in every group, which implies the repair is not only feasible but helpful for makespan.","The assembly order extracted from the repaired job sequence gives a direct way to schedule the assembly machine, so the same machinery handles both deadlock control and makespan computation."],"supporting_citations":[{"why":"Establishes that deadlock in DASP is closely tied to the order of finished jobs entering the assembly buffer, which is the premise IDAM repairs.","marker":"[10]"},{"why":"Supplies the supervisory-control notion that a marking is safe when the final state is reachable, the criterion IBA checks.","marker":"[38]"},{"why":"Provides the cooperative co-evolution framework with collaborators that HCCE's mCCEA structure adapts.","marker":"[40]"},{"why":"Defines the distributed assembly permutation flowshop problem and the benchmark design logic used to generate the test instances.","marker":"[1]"},{"why":"PBIGA is one of the three comparison algorithms HCCE is measured against.","marker":"[6]"},{"why":"HHMA is one of the three comparison algorithms HCCE is measured against.","marker":"[7]"},{"why":"EDMBO is one of the three comparison algorithms HCCE is measured against.","marker":"[8]"}],"fun_headline_variants":["Petri net repair makes assembly schedules deadlock-free","Hybrid co-evolution with Petri nets clears assembly deadlocks","Deadlock-prone assembly scheduling fixed by Petri net amendments","Co-evolution plus intelligent repair beats prior assembly schedulers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The deadlock-free guarantee is shown in a model where all jobs are available at time zero, and that model does not account for the timed order in which jobs actually finish in the factories.","fun_headline_variants_meta":{"raw":{"variants":["Petri net repair makes assembly schedules deadlock-free","Hybrid co-evolution with Petri nets clears assembly deadlocks","Deadlock-prone assembly scheduling fixed by Petri net amendments","Co-evolution plus intelligent repair beats prior assembly schedulers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000946,"raw_usage":{"total_tokens":4066,"prompt_tokens":1000,"completion_tokens":3066,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":3011}},"tokens_in":616,"tokens_out":3066,"duration_ms":22313,"temperature":1.0,"reasoning_tokens":3011,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:43:34.235391+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Forward-simulate any HCCE solution on the paper's smallest instance type using the processing times generated by the benchmark; if the backward makespan equations ever yield a negative start time, or the simulated buffer ever fills with jobs whose product is not completable, then the claimed IDAM guarantee plus backward calculation does not describe a realizable deadlock-free schedule.","supporting_citations":[{"cited_title":"Deadlock Control and Hybrid Social Spider Scheduling Algorithm for Two -stage Assembly Permutation Flowshop with Limited Buffers","cited_arxiv_id":null,"evidence_quote":"Establishes that deadlock in DASP is closely tied to the order of finished jobs entering the assembly buffer, which is the premise IDAM repairs."},{"cited_title":"The supervised control of discrete event dynamic systems: a new approach,","cited_arxiv_id":null,"evidence_quote":"Supplies the supervisory-control notion that a marking is safe when the final state is reachable, the criterion IBA checks."},{"cited_title":"A Population-Based Iterated Greedy Algorithm for Distributed Assembly No-Wait Flow-Shop Scheduling Problem,","cited_arxiv_id":null,"evidence_quote":"PBIGA is one of the three comparison algorithms HCCE is measured against."},{"cited_title":"An effective discrete monarch butterfly optimization algorithm for distributed blocking flow shop scheduling with an assembly machine,","cited_arxiv_id":null,"evidence_quote":"EDMBO is one of the three comparison algorithms HCCE is measured against."}],"review_version":1}