In the production scheduling of prefabricated components, a scheduling model considering the learning effect of processing time and the deterioration effect of delivery time in this paper is provided. More precisely, it asks for an assignment of a series of independent prefabricated jobs that arrived over time to a single machine for processing, and once the execution of a job is finished, it will be transported to the destination. The information of each prefabricated job including its basic processing time <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">$b_{j}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>b</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation>, release time <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">$r_j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>r</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation>, and deterioration rate <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">$e_j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>e</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> of delivery time is unknown in advance and is revealed upon the arrival of this job. Moreover, the actual processing time of prefabricated job <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$J_j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>J</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> with learning effect is <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="108" /> </InlineMediaObject> <EquationSource Format="TEX">$p_{j}=b_{j}(a-b t)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>p</mi> <mi>j</mi> </msub> <mo>=</mo> <msub> <mi>b</mi> <mi>j</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>a</mi> <mo>-</mo> <mi>b</mi> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where a and b are non-negative parameters and t denotes the starting time of prefabricated job <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$J_j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>J</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation>, respectively. And the delivery time of prefabricated job <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$J_j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>J</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">$q_{j}=e_{j}C_{j}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>q</mi> <mi>j</mi> </msub> <mo>=</mo> <msub> <mi>e</mi> <mi>j</mi> </msub> <msub> <mi>C</mi> <mi>j</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. The goal of scheduling is to minimize the maximum time by which all jobs have been delivered. For the problem, we first analyze offline optimal scheduling and then propose an online algorithm with a competitive ratio of <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1271_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="65" /> </InlineMediaObject> <EquationSource Format="TEX">$2-bb_{\min }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>-</mo> <mi>b</mi> <msub> <mi>b</mi> <mo movablelimits="true">min</mo> </msub> </mrow> </math></EquationSource> </InlineEquation>. Furthermore, the effectiveness of the online algorithm is demonstrated by numerical experiments and managerial insights are derived.

Single-machine scheduling with the learning effect of processing time and the deterioration effect of delivery time for prefabricated components

期刊论文
发表日期：

2025年3月13日

查看全文

Na Li,
Ran Ma,
Yuzhong Zhang

摘要

In the production scheduling of prefabricated components, a scheduling model considering the learning effect of processing time and the deterioration effect of delivery time in this paper is provided. More precisely, it asks for an assignment of a series of independent prefabricated jobs that arrived over time to a single machine for processing, and once the execution of a job is finished, it will be transported to the destination. The information of each prefabricated job including its basic processing time $b_{j}$ $b_{j}$ , release time $r_j$ $r_{j}$ , and deterioration rate $e_j$ $e_{j}$ of delivery time is unknown in advance and is revealed upon the arrival of this job. Moreover, the actual processing time of prefabricated job $J_j$ $J_{j}$ with learning effect is $p_{j}=b_{j}(a-b t)$ $p_{j} = b_{j} (a - b t)$ , where a and b are non-negative parameters and t denotes the starting time of prefabricated job $J_j$ $J_{j}$ , respectively. And the delivery time of prefabricated job $J_j$ $J_{j}$ is $q_{j}=e_{j}C_{j}$ $q_{j} = e_{j} C_{j}$ . The goal of scheduling is to minimize the maximum time by which all jobs have been delivered. For the problem, we first analyze offline optimal scheduling and then propose an online algorithm with a competitive ratio of $2-bb_{\min }$ $2 - b b_{min}$ . Furthermore, the effectiveness of the online algorithm is demonstrated by numerical experiments and managerial insights are derived.