# Stochastic Single Machine JIT Scheduling with Geometric Processing Times and Due Dates

Authors: Yuncheng Luo
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In this paper, we investigate a static stochastic single machine JIT scheduling problem in which the jobs’ processing times are stochastically independent and follow geometric distributions whose mean is provided, due dates are geometrically distributed with a common mean, and both the unit penalty of earliness/tardiness and the fixed penalty of earliness/tardiness are deterministic and different. The objective is to minimize the expected total penalties for quadratic earliness, quadratic tardiness, and early and tardy jobs. We prove that the optimal schedule to minimize this problem is V-shaped with respect to the ratio of mean processing time to unit tardiness penalty under the specific condition. Also, we show a special case and two theorems related to this JIT scheduling problem under specific situations where the optimal solutions exist. Finally, based on the V-shaped characteristic, a dynamic programming algorithm is designed to achieve an optimal V-shaped schedule in pseudopolynomial time.


---

## Body

## 1. Introduction

In just-in-time (JIT) scheduling, the decision maker intends to find a rational scheduling scheme so that all jobs will not be completed either too early or too late. In general, it is assumed that there are job due dates in the JIT scheduling model, and both earliness and tardiness are penalized. This paper tackles a scheduling model involving earliness and tardiness penalties in both quadratic and fixed form, that is, these penalties contain not only the variable charges hinging upon the quadratic earliness/tardiness of the jobs but also the fixed charges generated once the job is not punctually finished no matter how much the earliness/tardiness is. Hence, in order to avoid these penalties as much as possible, it is of great importance for decision maker to allocate the job due dates.The single machine environment plays a crucial role in scheduling theory. The performance of complex systems such as parallel machines generally depends on the schedule quality of a single bottleneck machine. Also, some results and insights obtained from the research of the single machine problems can be regarded to be valuable for solving the scheduling problems on more complex systems. The scheduling models with a single processor seem to appear frequently in practice. For the deterministic version of the models, researchers have studied many scheduling problems and obtained corresponding optimization results. Unfortunately, a large quantity of scheduling problems we encounter in practical are filled with many uncertain factors, so extending the model to the field of stochastic scheduling is an attempt to make the scheduling theory more practical. However, the research progress related to scheduling problem in the stochastic model has been slow. Hence, the scheduling problems under stochastic environment are still a significant and challenging research direction.The deterministic models related to single machine JIT scheduling problem have become an extensive research topic discussed since the later 1970s. Sidney [1] was one of the pioneers to study this class of scheduling problem. Kanet [2] proposed a constructive algorithm to find an optimal solution in polynomial time for the scheduling problem, where earliness and tardiness penalties are unit weights. Lann and Mosheiov [3], firstly, investigated the problem with the number of early and tardy jobs related to several cost structures by some heuristic algorithms. Later, there were many scheduling problems with earliness and tardiness penalties which have been studied in [4–6] by different algorithms, whilst this type of scheduling problem with controllable processing times was discussed in [7, 8], and the notion of job preemption in this type of scheduling problem was also examined in [9, 10]. The problems of minimizing the quadratic earliness and tardiness have also been considered. In [11–13], researchers, under different assumptions, considered the problem in which all quadratic earliness and tardiness penalties are equal, and this problem with symmetric weighted quadratic penalty function was also studied in [14, 15], while the asymmetric weighted version of this problem was investigated in [16–18]. The relevant scheduling problems with quadratic cost function have also been studied in [19, 20]. For the problems with more than two types of penalties, Lee et al. [21] developed a dynamic programming algorithm to solve two instances of the problem which includes a combination of three types of penalties, namely, earliness, tardiness, and tardy jobs. Shabtay [22] considered a case with the objective function ∑i=1nfdi+gEi+hTi, where f·, g·, and h· are nondecreasing functions. Koulamas [23] presented an algorithm for the 1di=d∑i=1nαd+βEi+γTi+δiVi+θiUiproblem. Baker and Scudder [24] presented an excellent survey for the initial research situations on both linear E-T and quadratic E-T scheduling problems, whilst a brilliant review of scheduling problems with multiple types of penalties was also provided in [25]. In [26, 27], the concept of batch in JIT scheduling problems with different objectives was investigated by several authors.Although there are most of JIT problems in which processing times and due dates are certain, jobs usually have random processing times and due dates in many practical situations. Surprisingly, there is little literature studied on scheduling problems in stochastic environments. Soroush and Fredendall [28] analyzed the single machine scheduling problem with normally distributed processing times and deterministic due dates to minimize the total expected earliness and tardiness penalties. Baker [29] studied the same case and obtained optimal solutions by designing a branch and bound algorithm. However, this problem was also considered in [30] when both processing times and due dates follow exponential distributions, and they derived the optimal V-shaped schedule by giving a dynamic programming algorithm. Liu and Liu [31] dealt with this type of problem in which release times and processing times are random variables. Cai and Zhou [32] investigated a problem with the three types of penalties, namely, earliness, tardiness, and flow time under normally distributed processing times and identically distributed due dates. Soroush [33] firstly explored the problem whose goal is to minimize the total expected weighted number of early and tardy jobs, where processing times are arbitrarily distributed, due dates are certain and jobs are penalized by fixed earliness weights and tardiness weights. The majority of the corresponding problems with E-T penalties have also been studied in [34–36] under distinct constraint conditions and assumptions. The stochastic version of problems with a relevant quadratic cost function has also been studied by several authors. Mittenthal and Raghavachari [37] analyzed a problem with quadratic earliness and tardiness penalties and stochastic machine breakdowns, whilst processing times are deterministic and due dates are common with certainty, and their objective is to minimize the expected value of the weighted sum of symmetric quadratic earliness and tardiness penalties of all jobs. Cai and Zhou [38] considered a similar case with uncertain uptimes and downtimes, but where both processing times and due dates are exponentially distributed. The problem of stochastically minimizing maximum lateness was analyzed in [39], where processing times and due dates follow exponential distribution. In [40], Soroush and Alqallaf investigated the stochastic problem of finding an optimal sequence that minimizes the total expected costs with weight quadratic tardiness penalties on a single machine, where idle time is not allowed, whilst the extending problem with initial idle time was examined in [41].In this paper, we, under stochastic scenario, address a static single machine JIT scheduling problem with the objective of minimizing the expected total penalties for quadratic earliness, quadratic tardiness, and early and tardy jobs. In this scheduling problem, it is assumed that processing times follow geometric distributions with distinct parameters and due dates follow geometric distributions with a common parameter. Geometric distribution is a commonly used discrete distribution, where there is only one parameter which represents the probability of success of the event, and the value range of geometric random variable is all positive integers. It is also one of the simplest forms in processing time distributions. Moreover, the jobs are penalized by variable weights depending on quadratic earliness/tardiness and fixed earliness/tardiness weights. These weights are distinct and job-dependent. We show that the optimal solution of this problem has V-shaped characteristic with respect to the ratio of mean processing time to unit tardiness penalty, that is, the schedule will first arrange jobs in nonincreasing order of the ratio of mean processing time to unit tardiness penalty and then arrange jobs in nondecreasing order of the ratio of mean processing time to unit tardiness penalty. To the best of the author’s knowledge, no other research, under geometrically distributed processing times and due dates, has studied this objective function which simultaneously incorporated the four types of penalty.This paper is structured as follows. Section2 defines and formulates a static single machine stochastic JIT scheduling problem. In Section 3, we obtain the V-shaped property of the optimal schedule for this problem and show a special case and two theorems related to this problem under specific situations where the optimal solutions exist. The designed dynamic programming is presented to obtain an optimal V-shaped schedule in Section 4. Section 5 is the conclusions.


## 2. Problem Definition and Formulation

Consider stochastic JIT scheduling problem that a setJ=1,2,…,n of n jobs are to be scheduled on a single machine. Assume that all jobs prepare for processing at time zero, and job preemption is not allowed that, as soon as a job starts to process on a single machine, it can not be disrupted until the process is finished. In addition, it is assumed that the machine which is always available can handle at most one job at a time, no machine breakdown occurs, and the machine inserted idle time are not allowed. In this problem, the processing time Pi of each job i is assumed to be independent random variable which follows geometric distribution with parameter 1/θi. Each job i has a due date Di which has geometric distribution with common parameter 1/δ, and Di is independent of Pi.sThe objective is to determine a scheduleπ that minimizes the expected total penalties for quadratic earliness, quadratic tardiness, and early and tardy jobs which can be formulated as follows:(1)ETPπ=E∑i=1nαiEi2+βiTi2+τiVi+φiUi,where π determines the order of processing the n jobs is a sequenceCiπ denotes the completion time of job i under πDi denotes the due date of job iEi denotes the earliness of job i, where Ei=max0,Di−CiπTi denotes the tardiness of job i, where Ti=max0,Ciπ−DiVi denotes the early indictor variable of job i, where Vi  = 1 if Ciπ<Di, otherwise, Vi=0Ui denotes the tardy indictor variable of job i, where Ui=1 if Ciπ>Di, otherwise, Ui=0αi≥0 is unit earliness penalty of job iβi≥0 is unit tardiness penalty of job iτi≥0 is fixed earliness penalty of job iφi≥0 is fixed tardiness penalty of job iEY represents the expectation of a random variable Y


## 3. The V-Shaped Characteristic of the Optimal Schedule

In this section, our goal is to obtain the structure characteristic of the optimal sequence that minimizesETPπ, and the objective in (1) can be equivalently expressed into(2)ETPπ=∑i=1nτi−φiPrDi>Ci+∑i=1nαi−βiEDi−Ci2IDi>Ci+∑i=1nβiECi−Di2+∑i=1nφi=ETP1π+ETP2π+ETP3π+∑i=1nφi,where IA is an indicative function, which takes value 1 when event A occurs; otherwise, it takes 0, and ETPiπ, i=1,2,3, are defined by(3)ETP1π=∑i=1nτi−φiPrDi>Ci,(4)ETP2π=∑i=1nαi−βiEDi−Ci2IDi>Ci,(5)ETP3π=∑i=1nβiECi−Di2.In order to tackle this scheduling problem, we first present a lemma below.Lemma 1.
If the processing timesPi,i=1,2,…,nare stochastically independent and geometrically distributed random variables with the mean θi,i=1,2,…,n, the due dates follow geometric distributions with a common mean δ, independent of Pi. Then, given an arbitrary schedule π=…,i,j,…, let π′=…,j,i,… denote the schedule that interchanges order of job i and jobj in π. Hence,(6)ETP1π−ETP1π′=φjθi−φiθj−τjθi−τiθjyiyjδ−1∏h∈Z∗yh,(7)ETP2π−ETP2π′=2δ2−δβjθi−βiθj−αjθi−αiθjyiyjδ−1∏h∈Z∗yh,(8)ETP3π−ETP3π′=βjθi−βiθj2∑h∈Z∗θh+2θi+2θj−2δ−1.Proof.
Due to the geometrically distributed ofPi and Di, we have EPi=θi, VarPi=σi2=θi2−θi, EDi=δ, and EDi2=2δ2−δ. Therefore, we have the expected completion time of job i under π:(9)ECi=∑h∈ZiEPh=∑h∈Ziθh,where Zi=Ziπ=…,i is the set of jobs which is to be processed before job i+1 in π. Since Di and Pi are geometrically distributed, which are stochastically independent, we have(10)PrDi>Pi=EPrDi>pi|Pi=pi=E∑n=pi+1+∞1δ1−1δn−1=E1−1δpi=∑n=1+∞1−1δn1θi1−1θin−1=δ−1θi+δ−1=yi,and(11)PrDi>Ci=E1−1δCi=E1−1δ∑h∈ZiPh=∏h∈ZiE1−1δPh=∏h∈Ziyh,where yh=δ−1/θh+δ−1, which implies(12)1−yi=θiθi+δ−1=θiyiδ−1.
Subsequently, by simple calculation, we have(13)EDi−Ci2IDi>Ci=EEDi−ci2IDi>ci|Ci=ci=E∑n=ci+1+∞n−ci21δ1−1δn−1=E∑x=1+∞x21δ1−1δx+ci−1=1δ∑x=1+∞x21−1δx−1E1−1δci=ED2∏h∈Ziyh=2δ2−δ∏h∈Ziyh,and then, by (11) and (13), we can define(14a)M1π=∑i=1nτi−φi∏h∈Ziyh,(14b)M2π=2δ2−δ∑i=1nαi−βi∏h∈Ziyh.
Hence, according to (14a) and (14b), the objective in (3) and (4) can, respectively, be rewritten by(15)ETP1π=M1π,and(16)ETP2π=M2π.
Following expectation and variance ofPi, we have(17)ECi2=E∑h∈ZiPh2+∑h∈Zi,h≠lPhPl=∑h∈ZiEPh2+∑h∈Zi,h≠lEPhEPl=∑h∈ZiEPh2+∑h∈ZiEPh2−∑h∈ZiEPh2=∑h∈ZiVarPh+∑h∈ZiEPh2=∑h∈Ziσh2+∑h∈Ziθh2,and by (9), (17), and Pi being independent of Di, the objective in (5) can be further written as(18)ETP3π=∑i=1nβiECi2−2EDiECi+EDi2i=∑i=1nβi∑h∈Ziσh2+∑i=1nβi∑h∈Ziθh2−2δ∑i=1nβi∑h∈Ziθh+2δ2−δ∑i=1nβi=M3π+M4π−2δM5π+2δ2−δ∑i=1nβi,where Miπ, i=3,4,5, are similarly defined by(19a)M3π=∑i=1nβi∑h∈Ziσh2,(19b)M4π=∑i=1nβi∑h∈Ziθh2,M5π=∑i=1nβi∑h∈Ziθh.
Thus, due to (15), (16), and (18) and VarPi=σi2=θi2−θi, (2) can be rewritten by(20)ETPπ=∑i=1nτi−φi∏h∈Ziyh+2δ2−δ∑i=1nαi−βi∏h∈Ziyh+∑i=1nβi∑h∈Ziθh2+∑i=1nβi∑h∈Ziθh2−2δ+1∑i=1nβi∑h∈Ziθh+2δ2−δ∑i=1nβi+∑i=1nφi.
LetZ∗=Ziπ−i=Zjπ′−j denote the set of jobs scheduled before job i in π(or before jobj in π′). Therefore, by (12) and (14a), under π and π′, we have(21)M1π−M1π′=τi−φiyi∏h∈Z∗yh+τj−φjyiyj∏h∈Z∗yh−τj−φjyj∏h∈Z∗yh−τi−φiyjyi∏h∈Z∗yh=τi−φiyi1−yj−τj−φjyj1−yi∏h∈Z∗yh=τi−φiyiθjyjδ−1−τj−φjyjθiyiδ−1∏h∈Z∗yh=φjθi−φiθj−τjθi−τiθjyiyjδ−1∏h∈Z∗yh,and according to (12), (14b), and similar process with (21),(22)M2π−M2π′=2δ2−δαi−βiyi∏h∈Z∗yh+αj−βjyiyj∏h∈Z∗yh−αj−βjyj∏h∈Z∗yh−αi−βiyjyi∏h∈Z∗yh=2δ2−δβjθi−βiθj−αjθi−αiθjyiyjδ−1∏h∈Z∗yh.
Substituting (21) into (15), (6) can be obtained, and substituting (22) into (16), (7) can be obtained.
Similarly, by (19a) and (19b),(23)M3π−M3π′=βi∑h∈Z∗σh2+σi2+βj∑h∈Z∗σh2+σi2+σj2−βj∑h∈Z∗σh2+σj2−βi∑h∈Z∗σh2+σj2+σi2=βjσi2−βiσj2=βjθi2−βiθj2+βiθj−βjθi,(24)M4π−M4π′=βi∑h∈Z∗θh+θi2+βj∑h∈Z∗θh+θi+θj2−βj∑h∈Z∗θh+θj2−βi∑h∈Z∗θh+θj+θi2=βjθi2∑h∈Z∗θh+2θj+θi−βiθj2∑h∈Z∗θh+2θi+θj=βjθi−βiθj2∑h∈Z∗θh+2θi+2θj+βiθj2−βjθi2,and(25)M5π−M5π′=βi∑h∈Z∗θh+θi+βj∑h∈Z∗θh+θi+θj−βj∑h∈Z∗θh+θj−βi∑h∈Z∗θh+θj+θi=βjθi−βiθj.
Substituting (23), (24), and (25) into (18), (8) can be obtained.
According to Lemma1, when both the processing times Pi and the due dates Di are geometrically distributed, we have the main result on the expected penalties of quadratic earliness, quadratic tardiness, and early and tardy jobs below.Theorem 1.
Assume that the processing timesP1,…,Pn are stochastically independent and geometrically distributed random variables with means θ1,…,θn, individually, and the due dates D1,…,Dn follow geometric distributions with a common mean δ, independent of Pi. Define(26a)Rij=φjθj−φiθi−1τjθj−τiθi,(26b)Sij=βjθj−βiθi−1αjθj−αiθi,Tij=βjθj−βiθi−1φjθj−φiθi,where Rij, Sij, and Tij are defined unless φjθi=φiθj or βjθi=βiθj. If Rij, Sij, and Tij satisfy the following condition,(27)Tij1−Rij−ykTjk1−Rjk+2δ2−δ1−Sij−yk1−Sjk<2θkδ−1for all different,i,j,k∈1,2,…,n,and the jobs are firstly arranged such that in nonincreasing order of θi/βi,i=1,2,…,j, then they are arranged such that, in nondecreasing order of θi/βi,i=j,j+1,…,n, for ∃j∈1,2,…,n, the schedule minimizes ETPπ. In other words, the optimal solutions given by the schedule are V-shaped with respect to the order of θi/βi.Proof.
By combining (6), (7), and (8) with (26a) and (26b), we obtain(28)ETPπ−ETPπ′=∑i=13ETPiπ−ETPiπ′=θiθjTijβjθj−βiθi−RijTijβjθj−βiθiyiyjδ−1∏h∈Z∗yh+θiθjβjθj−βiθi−Sijβjθj−βiθi2δ2−δδ−1yiyj∏h∈Z∗yh+θiθjβjθj−βiθi2∑h∈Z∗θh+2θi+2θj−2δ−1.
Then, by extracting common factor,(29)ETPπ−ETPπ′=θiθjβjθj−βiθi×∑h∈Z∗2θh+2θi+2θj+Tij1−Rijyiyjδ−1∏h∈Z∗yh+2δ2−δ1−Sijyiyjδ−1∏h∈Z∗yh−2δ−1.
Now, given a sequenceπ=…,i,j,k,…, then we denote the sequence π′=…,j,i,k,… which interchanges the order of job i and job j in π and the sequence π″=…,i,k,j,… which interchanges the order of job j and job k in π. Define(30)Gj=2∑h∈Z∗θh+2θj−1+2θj+Tj−1,j1−Rj−1,jyj−1yjδ−1∏h∈Z∗yh+1−Sj−1,j2δ2−δδ−1yj−1yj∏h∈Z∗yh,H=−2δ−1,for all i,j,k∈1,2,…,n, and then, we obtain(31)ETPπ−ETPπ′=θiθjβjθj−βiθiGj+Hand(32)ETPπ−ETPπ″=θjθkβkθk−βjθjGk+H.
IfGj+H<0 and according to the assumption of Theorem 1, the jobs are firstly handled such that(33)θjβj≥θj+1βj+1⇔βiθi≤βjθj.
Then, (31) implies(34)ETPπ−ETPπ′=θiθjβjθj−βiθiGj+H≤0.
IfGj+H≥0 and combining (27) and (30), we deduce that(35)Gk−Gj=2θk+ykTjk1−Rjkyiyjδ−1∏h∈Z∗yh+yk2δ2−δ1−Sjkyiyjδ−1∏h∈Z∗yh−Tij1−Rijyiyjδ−1∏h∈Z∗yh−2δ2−δ1−Sijyiyjδ−1∏h∈Z∗yh=2θk1−q2θkδ−1yiyj∏h∈Z∗yh>0,where q=Tij1−Rij−ykTjk1−Rjk+2δ2−δ1−Sij−yk1−Sjk. Hence, we obtain Gk−H>Gj−H≥0. Due to the assumption of Theorem 1, the jobs are secondly handled such that(36)θj+1βj+1≥θjβj⟺βkθk≤βjθj.
Then, (32) implies(37)ETPπ−ETPπ″=θjθkβkθk−βjθjGk+H≤0.
Thus, the result of Theorem1 is proved that an optimal sequence to minimize ETPπ is V-shaped with respect to θi/βi.
For distinctαi, βi, τi, and φi, a large quantity of cases are covered by Theorem 1. When the four weights are some constants, we discuss a special case below.
A special case: assume thatRij≡R, Sij≡S, and Tij≡T are some constants, then condition (27) is rewritten by(38)T1−R1−yk+2δ2−δ1−S1−yk<2θkδ−1.
IfR>1, S>1, and T>0, the above condition evidently holds. Therefore, θi/αi, θi/βi, θi/τi, and θi/φi have the same order. Hence, by Theorem 1, the optimal schedule is V-shaped with respect to θi/αi, θi/βi, θi/τi, or θi/φi.
In addition, we, under different assumptions, show two theorems related to thisETPπproblem where the optimal solutions exist.Theorem 2.
Assume thatmin1≤i≤nθi>δ, and Rij≡R, Sij≡S, and Tij≡T are some constants.(i)
If0<R<1, 0<S<1, and T>0, that is, θi/αi, θi/βi, θi/τi, and θi/φi have same orders, then ETPπ is minimized by the schedule in nondecreasing order of θi/αi, θi/βi, θi/τi, or θi/φi(ii)
IfR<0, S<0,and T>0, that is, θi/βi and θi/φi have the same orders, θi/αi and θi/τi have the same orders, and θi/βi and θi/αi have opposite orders, then ETPπis minimized by the schedule in nondecreasing order of θi/βi or θi/φi, or, equivalently, in nonincreasing order of θi/αi or θi/τi(iii)
IfR>1, S<0and T<0, that is, θi/αi, θi/τi, and θi/φi have same orders and θi/βi and θi/αi have opposite orders, then ETPπ is minimized by the schedule in nondecreasing order of θi/βi, or, equivalently, in nonincreasing order of θi/αi, θi/τi, or θi/φiTheorem 3.
Assume that∑i=1nθi<δ, and Rij≡R, Sij≡S, and Tij≡T are some constants.(i)
IfR>1, S>1, and T>0, that is, θi/αi, θi/βi, θi/τi, and θi/φi have the same orders, then ETPπ is minimized by the schedule in nonincreasing order of θi/αi, θi/βi, θi/τi, or θi/φi(ii)
If0<R<1, S>1, and T<0, that is, θi/βi and θi/αi have the same orders, θi/τiand θi/φi have the same orders, and θi/βi and θi/φi have opposite orders, then ETPπ is minimized by the schedule in nonincreasing order of θi/βi or θi/αi, or, equivalently, in nondecreasing order of θi/τi or θi/φi(iii)
IfR<0, S>1, and T<0, that is, θi/βi, θi/αi, and θi/τi have the same orders and θi/βi and θi/φihave opposite orders, then ETPπ is minimized by the schedule in nonincreasing order of θi/βi, θi/αi, or θi/τi, or, equivalently, in nondecreasing order of θi/φiProof.
Letθi/αi≤θj/αj, θi/βi≤θj/βj, θi/τi≤θj/τj, and θi/φi≤θj/φj; according to the assumption that min1≤i≤nθi>δ and the conditions of Part (i), we have Tij1−Rij>0 and 1−Sij>0. It follows from (29) that ETPπ−ETPπ′≤0. This proves that ETPπ−ETPπ′≤0 if and only if θi/αi≤θj/αj, θi/βi≤θj/βj, θi/τi≤θj/τj, or θi/φi≤θj/φj.
According to the similar proof procedure of Part (i), we can prove Part (ii), Part (iii), Part (iv), Part (v), and Part (vi).


## 4. Dynamic Programming Algorithm

In this section, in order to obtain the optimal solution of this stochastic problemETPπ among all V-shaped schedules, we propose dynamic programming algorithm based on Theorem 1 for the objective function (20). In general, it is necessary for the jobs to be numbered in nondecreasing order of θi/βi, i.e., θ1/β1≤θ2/β2≤…≤θn/βn. Then, think about a set of the jobs Ai=1,2,…,i for i∈1,2,…,n. Hence, job can be scheduled as the first or the last in this schedule for all the jobs in Ai if a schedule has a V-shaped characteristic. Suppose that π∗ is denoted as the optimal V-shaped schedule for the objective function (20) and Ai′ represents a set of the jobs is scheduled before those jobs in Ai under π∗. Let Ψi′=∏h∈Ai′yh,ϒi′=∑h∈Ai′θh,andΩi′=∑h∈Ai′θh2. Then, provided Ψi′, ϒi′, and Ωi′, fiΨi′,ϒi′,Ωi′ is defined as the contribution of all the jobs in Ai to the objective function (20). Afterwards, it is obvious that the contribution of the jobs if job i is the first and last job scheduled among all jobs in Ai is, respectively,(39a)fiaΨi′,ϒi′,Ωi′=fi−1Ψi′yi,ϒi′+θi,Ωi′+θi2+τi−φi+2δ2−δαi−βiΨi′yi+βiΩi′+θi2+ϒi′+θi2−2δ+1βiϒi′+θiand(39b)fibΨi′,ϒi′,Ωi′=fi−1Ψi′,ϒi′,Ωi′+τi−φi+2δ2−δαi−βiΨi′Ψi+βiΩi′+Ωi+ϒi′+ϒi2−2δ+1βiϒi′+ϒi,where Ψi=∏h∈Aiyh,ϒi=∑h∈Aiθh, and Ωi=∑h∈Aiθh2.On the basis of the optimal principle of dynamic programming, andfiaΨi′,ϒi′,Ωi′ and fibΨi′,ϒi′,Ωi′ are expressed in (39a) and (39b), respectively, hence the jobs are handled by the optimal V-shaped schedule such that(40)fiΨi′,ϒi′,Ωi′=minfiaΨi′,ϒi′,Ωi′,fibΨi′,ϒi′,Ωi′+2δ2−δ∑h∈Aiβi+∑h∈Aiφi.Thus, we can summarize the dynamic programming algorithm designed to achieve the optimal V-shaped schedule for this stochastic JIT problem.Since this is a dynamic programming algorithm, we can obtainπ∗according to its standard procedure, and the detailed process of the backward tracking is omitted. The algorithm is used to calculate all fiΨi′,ϒi′,Ωi′, at most OΨi′ϒi′Ωi′ steps, for each i. Thus, Algorithm 1 can derive the optimal schedule in OnΨi′ϒi′Ωi′ pseudopolynomial time for the stochastic single machine JIT problem.Algorithm 1:Dynamic programming.
Step 1: fori=1,2,…,n, we can calculate fiΨi′,ϒi′,Ωi′ by (39a), (39b), and (40) for all possible values Ψi′, ϒi′, and Ωi′.Step 2: defineFn∗=minΨn′,ϒn′,Ωn′fnΨn′,ϒn′,Ωn′Step 3: structure the optimal V-shaped scheduleπ∗ that obtains Fn∗ due to the backward tracking process


## 5. Conclusions

In this paper, we study a static stochastic single machine JIT scheduling problem in which the processing times are stochastically independent and geometrically distributed with distinct parameters, the due dates are geometrically distributed with a common parameter, and both the unit penalty of earliness/tardiness and the fixed penalty of earliness/tardiness are certain and distinct, where the JIT scheduling concept means that all the jobs are scheduled to complete as close to their due dates as possible. The objective is to find a schedule of jobs that minimizes the expected total penalties for quadratic earliness, quadratic tardiness, and early and tardy jobs. We show that an optimal schedule minimizing this problem has a V-shaped characteristic with respect toθi/βi by mathematical derivation under the specific condition (27). That is, the schedule will first arrange jobs in nonincreasing order of θi/βi and then arrange jobs in nondecreasing order of θi/βi. Nevertheless, there is a special case under three constants with specific value range, namely, Rij, Sij, and Tij, and then, the optimal solution obtained is V-shaped with respect to θi/αi, θi/βi, θi/τi, or θi/φi. Furthermore, we also give two theorems which contain a total of six situations related to this problem under different assumptions, and then, the optimal solution obtained is either monotonous nonincreasing or monotonous nondecreasing with respect to the ratio of mean processing time to different penalties. Finally, based on the V-shaped characteristic, we develop a dynamic programming algorithm which is designed to obtain an optimal V-shaped schedule in pseudopolynomial time.As a direction for the future research, it may be an interesting and significant challenge to consider this problem with other distributed processing times and due dates. In addition, this problem would be worth extending towards more complex systems such as parallel processors or dedicated processors.



---

*Source: 8874445-2021-05-18.xml*