Dispatching Rules for Minimizing Deviation from JIT Schedule Using the Earliness -Tardiness Scheduling Problem with Due Windows Approach

Dispatching Rules for Minimizing Deviation from JIT Schedule Using the Earliness -Tardiness Scheduling Problem with Due Windows Approach

Saheed Akande Ganiyu O. Ajisegiri Abdullah A. Adegoke Omolayo M. IkumapayiEsther T. Akinlabi 

Department of Mechanical and Mechatronics Engineering, Afe Babalola University, Ado Ekiti 360101, Nigeria

Department of Industrial and Production Engineering, University of Ibadan, Ibadan 200005, Nigeria

Pan African University for Life and Earth Sciences Institute (PAULESI), Ibadan 200001, Nigeria

Corresponding Author Email: 
Ikumapayi.omolayo@abuad.edu.ng
Page: 
377-385
|
DOI: 
https://doi.org/10.18280/jesa.550310
Received: 
25 May 2022
|
Accepted: 
10 June 2022
|
Published: 
30 June 2022
| Citation

OPEN ACCESS

Abstract: 

In Earliness-Tardiness (E/T) scheduling approach, the Just-In-Time (JIT) schedule is a schedule with zero earliness and zero tardiness. However, this is an optimal schedule and even notional in some instances where tardiness and earliness are inevitable. However, minimizing the deviation at the upper region (tardiness) and the lower region (earliness) from the JIT schedule is a challenge. This work proposes solutions. Two proposed heuristics; TA1 and TA2 as well as some existing heuristics were explored to solve simulated problems ranging from 5≤n≤400 and the results obtained were benchmarked against the JIT schedule. The results obtained show that one of the heuristics, TA2 yielded JIT schedules for many problem sizes at the lower and upper deviation than other solution methods.

Keywords: 

Just-In-Time (JIT), Earliness-Tardiness (E/T) scheduling problem, optimal schedule, deviation, heuristics

1. Introduction

There exist global economic meltdown and most production firms are faced with the challenges of optimizing profit. Therefore, minimizing sources of leakages and income losses like overproduction, high inventory cost, waiting and down tool time is a prerequisite. Just-In-Time (JIT) production has proved to be an essential requirement of world-class manufacturing concept [1]. This has made researchers to explore different variants of Earliness-Tardiness (E/T) scheduling problems to support the realization of JIT environment characterized by zero earliness, zero tardiness and zero inventories. However, JIT schedule is either an optimal schedule which is NP hard or even notional schedule and thus deviation is inevitable. In a due window approach, the due date has three components: The earliest due date, the original due date and the latest due date. The interval between the earliest and latest due date is called the due window [2]. This work proposes solution methods to minimize the deviation from the JIT schedule using the E/T scheduling problem with due window approach.

2. Literature Review

In a general scheduling system, penalty is usually associated with tardy and late jobs while early jobs are compensated. However, this is not always valid. Akande and Ajisegiri [3] discussed extensively three classes of Earliness – Tardiness scheduling problems and highlighted the variation of associated penalty with early jobs. The class three, as defined by the authors, associated penalty with both early and the tardy jobs. This is the concept of JIT production system. There is a global growing interest in JIT production, because the system ensures that all the jobs are completed at exactly due date or within the due windows and thus zero inventory is achieved [4]. Though several researchers have explored the Earliness- Tardiness scheduling problems but literature is sparse in which the problem is used to measure the deviation from the JIT schedule. This is the basis for this work. Nevertheless, Sourd [5] explored a dynamic programming procedure for solving the scheduling problems of minimizing the penalties associated with not delivering on time (JIT) and the idleness cost using the deviation in earliness–tardiness function. Also, authors like [6, 7] considered the problem of minimizing the weighted earliness and tardiness on a single machine. The dynamic variant of E/T scheduling problems was explored by Mazzini and Armentano [8] and the results obtained were used as a benchmark by Oyetunji and Oluleye [9] for two proposed two heuristics named ETA1 and ETA2. In this work, static variant of E/T scheduling problem with the due windows approach is considered and explored to measure the deviation from the JIT schedule. Liman et al; Janiak and Marek; Zhu, et al. [10-12] among others are some of researchers that have also explored various functions of due windows for scheduling problems.

3. Materials and Method

3.1 Assumptions and notations

The assumptions made in solving the problem are outlined for clarity as follows:

  1. The problem is deterministic with each job has a known processing time and a due window of known size.
  2. The problem is subjected to a static constraint.
  3. The machine is available continually and can process a job at a time with all the jobs are available at the same time.
  4. Pre-emption is not allowed, and all the data are integer.

Some notations are also employed, and they are presented in Table 1.

Table 1. Notations used for solving the problem

I

Job position $\mathrm{i}=1,2, \ldots, \mathrm{n}$

N

Number of Jobs

$p_{i}$

Processing time of job i

$C_{i}$

Completion time of Job i

$\mathrm{d}_{\mathrm{j}}$

Original Due date of Job i

$D_{i}^{e}$

Earliest due date of job i

$D_{i}^{L}$

Latest due date of job i

$\mathrm{E}_{\mathrm{I}}$

Earliness of Job i

$\mathrm{T}_{\mathrm{i}}$

Tardiness of Job i

$\mathrm{L}_{\mathrm{i}}$

Lateness of Job i

$N_{J I T}$

Number of Just in Time Jobs

UD

Upward Deviation

DD

Downward Deviation

DOD

Degree of Deviation

NSG

Deviation value less than 1 (unit)

SG

Deviation value greater than 1 (unit)

SPT

Shortest Processing Time

MDD

Modified Due Date

FCFS

First Come First Schedule

EDD

Earliest Due Date

3.2 Problem definition

Consider an automobile servicing firm with only one technician working on a service bay and one service advisor for customers scheduling and appointment. For every job completed after the allocated due window given to the customer, there is always a penalty either in terms of goodwill or reduction in the service charge. Also, for all the jobs completed before the due window, there is an associated cost with parking the car (inventory cost) [13, 14]. Therefore, a system where the completed vehicle is released to the customer at the point of completion will eliminate not only the inventory cost but also the penalty cost associated with lateness or tardiness. Such a system is a typical JIT system. At this point, it is expected that $\mathrm{d}_{\mathrm{i}}=\mathrm{C}_{\mathrm{i}}$.

The total number of jobs completed within the due window is given by

$N_{J I T}=\sum_{i=1}^{n} J I T_{i}$        (1)

where

$J I T_{i}=\left\{\begin{array}{c}1 \text { if } \mathrm{d}_{i}=\mathrm{C}_{i} \\ 0 \text { Otherwise }\end{array}\right.$         (2)

If JIT system is achieved, for $i=1,2, \ldots, n$

$\mathrm{d}_{i}=\mathrm{C}_{i}$       (3)

$\mathbf{n}=N_{J I T}=\sum_{i=1}^{n} J I T_{i}$        (4)

Also, the tardiness of each jobs, i and total tardiness of all the jobs will be given by

$\boldsymbol{T}_{i}=\max \left\{0,\left(\mathrm{C}_{i}-\mathrm{d}_{i}\right)\right\}=0$        (5)

$T_{\text {tot }}=\sum_{i=1}^{n} \boldsymbol{T}_{i}=\mathbf{0}$       (6)

Similarly, the earliness of each jobs, i and the total earliness of all the jobs will be given by

$E_{i}=\max \left\{-L_{i}, 0\right\}=0$        (7)

$E_{\text {tot }}=\sum_{i=1}^{n} E_{i}=0$        (8)

However, it is not feasible to always attain JIT condition, thus

$\mathbf{n} \gg N_{J I T}$        (9)

$T_{i} \geq 0$       (10)

$T_{\text {tot }} \geq 0$      (11)

$E_{i} \geq 0$      (12)

$E_{\text {tot }} \geq 0$       (13)

However, the target is to minimize these inevitable deviations which are the upward curve deviation associated with the tardiness (jobs completed after the due date) and the downward curve deviation associated with the earliness (job completed earlier than the due dates). Therefore, the deviation in JIT can be described as a piecewise function with the $T_{\text {tot }}$ in the upper region domain and the $E_{\text {tot }}$ in the lower region domain. This condition is illustrated in Figure 1.

Figure 1. Completion time against due date to show deviation from JIT

Therefore, if the total tardiness (upward deviation) and the total earliness (downward deviation) are minimized simultaneously with respect to the equilibrium or JIT values, then the total deviation is also minimized. The two solution methods proposed are hereby discussed.

3.3 Proposed solution methods

The steps of the heuristics are stated as follows.

TA1 ALGORITHM: This algorithm is based on the theorem stated below:

When solving the $\sum_{i=1}^{n} E_{i}+\sum_{i=1}^{n} T_{i}$ for any two jobs say j and K, there exists an optimal sequence for which j appear before k if the following conditions hold:

I. $P_{\mathrm{j}} \leq P_{k}$        (14)

II. $\mathrm{D}_{\mathrm{j}} \leq D_{k}$      (15)

For due windows, this corollary is still valid.

If the Eqns. (14) and (15) are valid then, it can be deduced that: $\mathrm{P}_{\mathrm{j}}+\mathrm{D}_{\mathrm{j}} \leq P_{k}+\mathrm{D}_{\mathrm{k}}$.

Therefore, the steps of the TA1 heuristics are outlined as follows:

STEP 1: Compute the factor time (P+D) for the jobs in job set A.

STEP 2: Arrange the jobs set A in order of increasing Factor Time (P+D) and put the same in Job set C. If there is a tie set, break the tie arbitrarily.

STEP 3: Set i=1 where i is the index number of the job in job set C and update Job Set B with job, i and remove the same job from Job set C. If there is a tie, update Job Set B with the job that has the lowest due date among the tie jobs. Continue until all the jobs have been updated. Job set B is the required sequence.

STEP 5: Compute the earliness and the tardiness of each of the job in the Job Set B.

STEP 8: Stop

TA 2 ALGORITHM

The statements of the TA2 heuristics are outlined as follows:

STEP 1: Arrange the jobs Set A in the order of increasing Factor Time (P + D) and put the same in Job Set C. if there is a tie break the tie arbitrarily.

STEP 2: Arrange Job Set A using the MDD and put same in job Set B.

STEP 3: Compute the earliness and the tardiness of each of the jobs in the Job set B and Job set C.

STEP 4: Compute the FUNCTION $E_{i}+T_{i}$ of each of the jobs in the Job set B and Job set C.

STEP 5: Combine the two schedules by scheduling the job at the same level and with the minimum FUNCTION $E_{i}+T_{i}$ and which has not been previously scheduled.

STEP 6: Remove any jobs that existed more than once. Compute the length of the resultant schedule. Called the schedule Job Set C.

STEP 7: If the length of Job Set C is equal to the length of the job set A. Then Job Set C is the required schedule Then go to step 9. Else go to step 8.

STEP 8: Subtract Job Set C from Job Set A to obtain the jobs that have not been scheduled. Thus, Job Set H = Job Set C – Job Set A.

STEP 9: Arrange job set H at the back of job set C in increasing order of due date. This is called Job set P.

STEP 10: Compute the tardiness and the total tardiness of the optimal sequence schedule.

STEP 11: Stop

3.4 Problem generation for simulation

The utilities of the proposed solution methods were demonstrated by simulated some single processor scheduling problems using the desktop tool module (editor) from MATLAB R2010 programming language. Equations explored by Suer et al. [15]; Akande and Ajisegiri, [16]; Sunday et al. [17]; Bedhief and Dridi [18]; and Joshi and Satpathy [19] were modified to generate the required parameters which include the processing time and the due windows as follows:

$D_{j}=R_{j}+K P_{j}$      (16)

$D_{j}^{L / E}=D_{j} \pm\left(A_{j} \times D_{j}\right)$      (17)

$D_{j}^{e}=D_{j}-\left(D_{j} \times A_{j}\right)$       (18)

$D_{j}^{L}=D_{j}+\left(D_{j} \times A_{j}\right)$       (19)

where,

$D_{j}^{e}$: is the earliest due date for job j.

$D_{j}$: is the original due date.

$D_{j}^{L}$: is the latest due date for job j.

Aj: is the flow allowance assigned to job j at time zero. Is set at (20% - 40% of $D_{j}$).

In this simulating experiment, the proposed solution methods as well as the existing ones (SPT, EDD, MDD and FCFS) were tested with the three components of the due windows.

4. Results and Discussion

The results of the computational experiment are grouped into two classes. Tables 2 – 12 show the results of the total earliness and the tardiness and the Degree of Deviation (DOD) for each of the considered problem sizes for all the solution methods for the three due window components. Table 13, Table 14 and Table 15 show the value of the tardiness for the early due window, original due window, and the latest due window respectively. Table 16, Table 17, and Table 18 show the value of earliness for the early due window, original due window, and the latest due window respectively. However, it should be noted that the value of the earliness and the tardiness for the notional JIT schedule is zero for all the problem sizes. Furthermore, Figure 2, Figure 3, and Figure 4 illustrate the degree of deviation of the total tardiness (Upper deviation) from the notional JIT in the early due window, original due window, and the latest due window respectively, while Figure 5, Figure 6 and Figure 7 show the lower deviation (Total earliness) in the three windows respectively.

Table 2. Results of the total Earliness and Tardiness and the degree of deviation for 5 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

29.65

2.85

SG

NSG

0.00

118.00

JIT

SG

0.00

35.85

JIT

SG

MDD

28.35

0.55

SG

NSG

0.00

8.00

JIT

SG

0.00

35.85

JIT

SG

TA1

28.35

0.55

SG

NSG

0.00

117.00

JIT

SG

0.00

35.85

JIT

SG

TA2

28.35

0.55

SG

NSG

0.00

47.00

JIT

SG

0.00

35.85

JIT

SG

FCFS

35.35

0.55

SG

NSG

12.00

15.00

SG

SG

3.50

34.35

SG

SG

EDD

30.35

0.55

SG

NSG

0.00

117.00

JIT

SG

0.00

35.85

JIT

SG

Table 3. Results of the total Earliness and Tardiness and the degree of deviation for 10 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

135.0

0.96

SG

NSG

9.0

158.00

SG

SG

82.0

25.60

SG

SG

MDD

135.0

0.95

SG

NSG

29.0

3.00

SG

SG

67.0

6.20

SG

SG

TA1

139.0

0.95

SG

NSG

0.00

118.00

JIT

SG

73.0

8.35

SG

SG

TA2

135.0

0.95

SG

NSG

29.0

3.00

SG

SG

67.0

6.20

SG

SG

FCFS

225.0

6.65

SG

SG

20.0

32.00

SG

SG

162.0

42.80

SG

SG

EDD

139.0

0.95

SG

NSG

0.00

104.00

JIT

SG

80.0

6.20

SG

SG

Table 4. Results of the total Earliness and Tardiness and the degree of deviation for 15 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

350.0

0.00

SG

JIT

107.0

107.0

SG

SG

203.0

14.70

SG

SG

MDD

350.0

0.00

SG

JIT

200.0

7.0

SG

SG

1.97.0

6.00

SG

SG

TA1

359.0

0.00

SG

JIT

105.0

40.0

SG

SG

222.0

3.15

SG

SG

TA2

350.0

0.00

SG

JIT

118.0

34.0

SG

SG

197.0

6.00

SG

SG

FCFS

543.0

6.30

SG

SG

196.0

25.0

SG

SG

401.0

26.80

SG

SG

EDD

366.0

0.00

SG

JIT

118.0

34.0

SG

SG

244.0

2.75

SG

SG

Table 5. Results of the total Earliness and Tardiness and the degree of deviation for 20 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

8.08e+2

1.25

SG

SG

2.97e+2

147.00

SG

SG

3.67e+2

5.50

SG

SG

MDD

8.07e+2

0.00

SG

JIT

5.23e+2

2.00

SG

SG

3.69e+2

1.75

SG

SG

TA1

8.30e+2

0.00

SG

JIT

3.03e+2

50.00

SG

SG

3.94e+2

4.80

SG

SG

TA2

8.07e+2

0.00

SG

JIT

4.39e+2

13.00

SG

SG

3.69e+2

1.75

SG

SG

FCFS

11.89e+2

0.00

SG

JIT

4.49e+2

28.00

SG

SG

6.83e+2

12.25

SG

SG

EDD

8.71e+2

0.00

SG

JIT

3.47e+2

41.00

SG

SG

4.07e+2

1.75

SG

SG

                         

Table 6. Results of the total Earliness and Tardiness and the degree of deviation for 40 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

2.84e+3

0.00

SG

JIT

2.29e+3

159.00

SG

SG

1.64e+3

1.40

SG

SG

MDD

2.84e+3

0.00

SG

JIT

2.98e+3

3.00

SG

SG

1.64e+3

0.35

SG

NSG

TA1

2.89e+3

0.00

SG

JIT

2.64e+3

32.00

SG

SG

1.70e+3

0.35

SG

NSG

TA2

2.84e+3

0.00

SG

JIT

2.87e+3

6.00

SG

SG

1.64e+3

0.35

SG

NSG

FCFS

4.00e+3

5.40

SG

SG

3.31e+3

24.00

SG

SG

2.70e+3

17.15

SG

SG

EDD

2.96e+3

0.00

SG

JIT

2.76e+3

25.00

SG

SG

1.73e+3

0.35

SG

NSG

Table 7. Results of the total Earliness and Tardiness and the degree of deviation for 50 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

3790

0.95

SG

NSG

3360

144

SG

SG

3020

3.05

SG

SG

MDD

3790

0.00

SG

JIT

4430

7.00

SG

SG

3010

0.35

SG

NSG

TA1

3910

0.00

SG

JIT

3990

29.00

SG

SG

3170

0.35

SG

NSG

TA2

3790

0.00

SG

JIT

4340

14.00

SG

SG

3010

0.35

SG

NSG

FCFS

6120

0.00

SG

JIT

5340

29.00

SG

SG

4640

20.1

SG

SG

EDD

4050

0.00

SG

JIT

4300

26.00

SG

SG

3270

0.35

SG

NSG

Tables 2-12 reveal that the two proposed performance measures yielded better results than the selected existing solution methods. This is because the results of TA1 and TA2 yielded a more optimal JIT schedule in the three windows at both the upper deviation (total Tardiness) and the lower deviation (Total earliness) in the three windows components. Also, FCFS yielded the worst results among all the solution methods for each of the problem sizes. However, to measure the performance of the solution over the range of the considered problem sizes (5-400), Tables 13-18 also shows the values of the total earliness and the tardiness at each of the window’s components. Figure 2 - Figure 7 also shows the deviation graphically.

Figure 2 shows that FCFS has the highest upper deviation. The SPT also has a higher deviation especially for the lower number of jobs. As the number of jobs increases, the performance of SPT, EDD, and the two proposed solution methods (TA1 and TA2) coincides.

Table 8. Results of the total Earliness and Tardiness and the degree of deviation for 100 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

LCOF

UD

LD

UD

LD

UD

LD

SPT

17900

0.30

SG

NSG

16400

260.00

SG

NSG

16200

1.05

SG

SG

MDD

17900

0.00

SG

JIT

20200

1.00

SG

NSG

16204

0.35

SG

NSG

TA1

18500

0.00

SG

JIT

19400

6.00

SG

NSG

17100

0.35

SG

NSG

TA2

17900

0.00

SG

JIT

19900

4.00

SG

NSG

16200

0.35

SG

NSG

FCFS

25900

4.50

SG

SG

23300

17.00

SG

NSG

22600

23.0

SG

SG

EDD

19300

0.00

SG

JIT

20200

4.00

SG

NSG

17400

0.35

SG

NSG

Table 9. Results of the total Earliness and Tardiness and the degree of deviation for 150 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

3.819e+4

0.95

SG

NSG

3.606e+4

312

SG

SG

3.344e+4

2.80

SG

SG

MDD

3.819e+4

0.00

SG

JIT

4.386e+4

1.00

SG

SG

3.343e+4

0.35

SG

NSG

TA1

3.924e+4

0.00

SG

JIT

4.176e+4

1.00

SG

SG

3.500e+4

0.35

SG

NSG

TA2

3.819e+4

0.00

SG

JIT

4.386e+4

1.00

SG

SG

3.343e+4

0.35

SG

NSG

FCFS

5.468e+4

8.80

SG

SG

5.152e+4

13.00

SG

SG

5.092e+4

46.15

SG

SG

EDD

4.067e+4

0.00

SG

JIT

4.417e+4

1.00

SG

SG

3.596e+4

0.35

SG

NSG

Table 10. Results of total Earliness and Tardiness and the degree of deviation for 200 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

6.679e+4

0.30

SG

NSG

6.051e+4

356.00

SG

SG

6.721e+4

0.35

SG

NSG

MDD

6.679e+4

0.00

SG

JIT

7.728e+4

2.00

SG

SG

6.721e+4

0.35

SG

NSG

TA1

6.860e+4

0.00

SG

JIT

7.335e+4

15.00

SG

SG

7.095e+4

0.35

SG

NSG

TA2

6.679e+4

0.34

SG

NSG

7.689e+4

5.00

SG

SG

6.721e+4

0.35

SG

NSG

FCFS

9.690e+4

5.35

SG

SG

9.220e+4

19.00

SG

SG

9.815e+4

33.65

SG

SG

EDD

7.134e+4

0.00

SG

JIT

7.734e+4

8.00

SG

SG

7.279e+4

0.35

SG

NSG

Table 11. Results of total Earliness and Tardiness and the degree of deviation for 300 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

1.661e+5

0.30

SG

NSG

1.560e+5

303.00

SG

SG

1.605e+5

4.80

SG

SG

MDD

1.661e+5

0.30

SG

NSG

1.870e+5

0.00

SG

JIT

1.605e+5

0.00

SG

JIT

TA1

1.715e+5

0.00

SG

JIT

1.812e+5

0.00

SG

JIT

1.673e+5

0.35

SG

NSG

TA2

1.661e+5

0.00

SG

JIT

1.870e+5

0.00

SG

JIT

1.605e+5

0.00

SG

JIT

FCFS

2.342e+5

4.45

SG

SG

2.157e+5

24.00

SG

SG

2.267e+5

29.50

SG

SG

EDD

1.779e+5

0.00

SG

JIT

1.894e+5

0.00

SG

JIT

1.712e+5

0.35

SG

NSG

Table 12. Results of total Earliness and Tardiness and the degree of deviation for 400 x 1 problem size

 

Earliest Due Date

Original Due Date

Latest Due Date

Solution Method

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

$\sum_{i=1}^{n} T_{i}$

$\sum_{i=1}^{n} E_{i}$

DOD

UD

LD

UD

LD

UD

LD

SPT

2.677e+5

0.00

SG

JIT

2.708e+5

304

SG

SG

2.749e+5

3.05

SG

SG

MDD

2.677e+5

0.00

SG

JIT

3.240e+5

0.00

SG

JIT

2.749e+5

0.35

SG

NSG

TA1

2.750e+5

0.00

SG

JIT

3.161e+5

1.00

SG

SG

2.876e+5

0.35

SG

NSG

TA2

2.677e+5

0.00

SG

JIT

3.240e+5

0.00

SG

JIT

2.749e+5

0.35

SG

NSG

FCFS

3.846e+5

2.85

SG

SG

3.826e+5

10.00

SG

SG

3.876e+5

28.85

SG

SG

EDD

2.869e+5

0.00

SG

JIT

3.302e+5

1.00

SG

SG

2.946e+5

0.35

SG

NSG

In the original due date window, as revealed in Figure 3, all the solution methods except FCFS yielded the JIT schedule for 5x1 problem size while only EDD, TA1, and TA2 also yielded JIT schedule for 10x1 problem sizes. However, as the job size increases, the upper deviation increase with SPT has the lowest deviation at 400x1 problem sizes.

In the latest due date window, as revealed in Figure 4, all the solution methods except FCFS yielded the JIT schedule for the 5x1 problem size. However, as the job size increases, the upper deviation increases with SPT, MDD, and TA2 coincides with the lowest deviation at 400x1 problem sizes while FCFS and TA1 has the highest deviation.

The results of lower deviation (Total earliness) were erratic. Though most of the solution method yielded a JIT schedule for most of the problem sizes, the results of FCFS and SPT shows the highest deviation.

Figure 6 reveals that SPT yielded the highest deviation from the JIT schedule for all the problem sizes.

Also, TA1 and EDD show high deviation for problem sizes, n≤50.

Table 13. The Tardiness value for the Earliest due date window for all the solution methods

Problem size

JIT SCHEDULE

SPT

MDD

EDD

FCFS

TA1

TA2

5X1

0

29.65

28.35

30.35

35.35

28.35

28.35

10X1

0

135

135

139

225

139

135

15 X1

0

350

350

366

543

359

350

20X1

0

808

807

871

1190

830

807

40x1

0

2840

2840

2960

40000

2890

2840

50x1

0

3790

3790

4050

6120

3910

3790

100x1

0

17900

17900

19300

25900

18500

17900

200x1

0

66790

66790

71340

96900

68600

66790

300x1

0

166100

166100

177900

234200

171500

166100

400x1

0

267700

267700

286900

384600

275000

267700

Figure 2. Plot of Total tardiness against the Problem sizes for the early due date window

Table 14. The Tardiness value for the Original due date window for all the solution methods

Problem size

JIT SCHEDULE

SPT

MDD

EDD

FCFS

TA1

TA2

5X1

0

0

0

0

12

0

0

10X1

0

9

29

0

20

0

0

15 X1

0

107

200

118

196

118

105

20X1

0

297

523

347

449

303

439

40x1

0

2290

2980

2760

3310

2640

2870

50x1

0

3790

3790

4050

6120

3910

3790

100x1

0

16400

20200

20200

23300

19400

19900

200x1

0

60510

77280

77340

92200

73350

76890

300x1

0

156000

187000

189400

215700

181200

187000

400x1

0

270800

324000

330200

382600

316100

324000

Figure 3. Plot of Total tardiness against the Problem sizes for the original due date window

Table 15. The Tardiness value for the Latest due date window for all the solution methods

Problem size

JIT SCHEDULE

SPT

MDD

EDD

FCFS

TA1

TA2

5X1

0

0

0

0

3.5

0

0

10X1

0

82

67

80

162

73

67

15 X1

0

203

197

244

401

222

197

20X1

0

367

369

407

683

394

369

40 x1

0

1640

1640

1730

2700

1700

1640

50x10

0

3020

3010

3270

4640

3170

3010

100x1

0

16200

16200

17400

22600

17100

16200

150 x1

0

33440

33430

35960

50920

35000

33430

200x1

0

67210

67210

72790

98150

150000

67210

300x1

0

160500

160500

171200

226700

167300

160500

400x1

0

274900

274900

294600

387600

287600

274900

Figure 4. Plot of Total tardiness against the Problem sizes for the latest due date window

Table 16. The total Earliness value for Early Due Date Earliness for all the solution methods

Problem size

 JIT SCHEDULE

SPT

MDD

EDD

FCFS

TA1

TA2

5X1

0

2.85

0.55

0.55

0.55

0.55

0.55

10X1

0

0.96

0.95

0.95

6.65

0.95

0.95

15 X1

0

0

0

0

6.3

0

0

20X1

0

1.25

0

0

0

0

0

40x1

0

0

0

0

5.4

0

0

50 x 1

0

0.95

0

0

0

0

0

100 x 1

0

0.3

0

0

4.5

0

0

150 x 1

0

0.95

0

0

8

0

0

200 x 1

0

0.3

0

0

5.35

0

0.34

300 x 1

0

0.3

0.3

0

4.45

0

0

400 x 1

0

0

0

0

2.85

0

0

Figure 5. Plot of Total earliness against the Problem sizes for the early due date window

Table 17. The Earliness value for the Original due date window for all the solution methods

Problem size

JIT Schedule

SPT

MDD

EDD

FCFS

TA1

TA2

5X1

0

118

8.00

117

15

117.0

47

10X1

0

158.0

3.0

104

32

118

3.0

15 X1

0

107

7.00

34

25

40

34

20X1

0

147

2.00

41

28

50

13

40 x1

0

159

3.00

25.00

24.00

32.00

6.00

50x10

0

144.00

7.00

26.00

29.00

29.00

14.00

100x1

0

260.00

1.00

4.00

17.00

6.00

4.00

150 x1

0

312

1.00

1.00

13.00

1.00

1.00

200x1

0

356.00

2.00

8.00

19.00

15.00

5.00

300x1

0

303.00

0.00

0.00

24.00

0.00

0.00

400x1

0

304

0.00

10.00

1.00

1.00

0.00

Figure 6. Plot of Total earliness against the Problem sizes for the original due date window

Table 18. The total earliness value for the Latest Due Date window for all the solution methods

Problem size

JIT SCHEDULE

SPT

MDD

EDD

FCFS

TA1

TA2

5X1

0

35.85

35.85

35.85

34.85

35.85

35.85

10X1

0

25.6

6.2

6.2

42.8

8.35

6.2

15 X1

0

14.7

6

2.75

26.8

3.15

6

20X1

0

5.5

1.75

1.75

12.25

4.8

1.75

40 x1

0

1.4

0.35

0.35

17.15

0.35

0.35

50x10

0

3.05

0.35

0.35

20.1

0.35

0.35

100x1

0

1.05

0.35

0.35

23.05

0.35

0.35

150 x1

0

2.8

0.35

0.35

46.15

0.35

0.35

200x1

0

0.35

0.35

0.35

33.65

0.35

0.35

300x1

0

4.8

0

0.35

29.5

0.35

0

400x1

0

3.05

0.35

0.35

28.85

0.35

0.35

Figure 7. Plot of Total earliness against the Problem sizes for the latest due date window

Figure 7 reveals that FCFS and SPT yielded the highest deviation from the JIT schedule for all the problem sizes. Also, other solution methods show higher deviation at problem sizes; n$\leq$40. As the problem sizes exceeded this limit, the deviation becomes not significant for all the solution methods except FCFS and SPT.

5. Conclusions

This work proposed two heuristics for Earliness-Tardiness scheduling problems as a means of measuring the deviation of a schedule from the notional JIT Schedule. The results obtained revealed that one of the proposed heuristics TA2 yielded a lower deviation at both the upper and the lower region compared to other proposed heuristics (TA1) and other selected solution methods from the literature.

The work can be explored further by expressing the results of the total earliness and tardiness in composite function using any form of the mathematical expression be it linear, quadratic, or arbitrary equations. However, normalization must be carried for the LCOF using the notional JIT as the benchmark to avoid unbalanced and skewed normalized results.

  References

[1] Sabuncuoglu, I., Lejmi, T. (1999). Scheduling for non regular performance measure under the due window approach. Omega, 27(5): 555-568. https://doi.org/10.1016/S0305-0483(99)00018-3

[2] Janiak, A., Janiak, W., Marek, M. (2009). Single processor scheduling problems with various models of a due window assignment. Bulletin of the Polish Academy of Sciences: Technical Sciences, 95-101. https://doi.org/10.2478/v10175-010-0110-7

[3] Akande, S., Ajisegiri, G. (2022). Three classes of Earliness-Tardiness (E/T) scheduling problems. Fuel Communications, 10: 100047. https://doi.org/10.1016/j.jfueco.2021.100047

[4] Józefowska, J. (2007). Just-in-time scheduling: models and algorithms for computer and manufacturing systems. Boston, MA: Springer US. 49-129. https://doi.org/10.1007/978-0-387-71718-0_3

[5] Sourd, F. (2005). Punctuality and idleness in just-in-time scheduling. European Journal of Operational Research, 167(3): 739-751. https://doi.org/10.1016/j.ejor.2004.07.018

[6] Chen, H., Chu, C., Proth, J.M. (1995). A branch and bound approach for earliness-tardiness scheduling problems with different due dates (Doctoral dissertation, INRIA). 

[7] Wan, G., Yen, B.P.C. (2002). Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. European Journal of Operational Research, 142(2): 271-281. https://doi.org/10.1016/S0377-2217(01)00302-2

[8] Mazzini, R., Armentano, V.A. (2001). A heuristic for single machine scheduling with early and tardy costs. European Journal of Operational Research, 128(1): 129-146. https://doi.org/10.1016/S0377-2217(99)00345-8

[9] Oyetunji, E., Oluleye, A.E. (2011). Minimizing total earliness and total tardiness on single machine with release dates. In International Journal of Engineering Research in Africa, 5: 30-43. https://doi.org/10.4028/www.scientific.net/JERA.5.30

[10] Liman, S.D., Panwalkar, S.S., Thongmee, S. (1998). Common due window size and location determination in a single machine scheduling problem. Journal of the Operational Research Society, 49(9): 1007-1010. https://doi.org/10.1057/palgrave.jors.2600601

[11] Zhu, C., Jiang, F.C., Tang, Y.L. (2022). Joint scheduling of charging and service operation of electric taxi based on reinforcement learning. Journal Européen des Systèmes Automatisés, 55(2): 267-272. https://doi.org/10.18280/jesa.550215

[12] Janiak, A., Marek, M. (2003). Scheduling problems with optimal due interval assignment subject to some generalized criteria. In Operations Research Proceedings, pp. 217-222. https://doi.org/10.1007/978-3-642-55537-4_35

[13] Okokpujie, I.P., Okokpujie, K., Omidiora, O., Oyewole, H.O., Ikumapayi, O.M., Emuowhochere, T.O. (2022). Benchmarking and multi-criteria decision analysis towards developing a sustainable policy of just in time production of biogas in Nigeria. Planning, 17(2): 433-440. https://doi.org/10.18280/ijsdp.170208

[14] Afolalu, S.A., Ikumapayi, O.M., Ongbali, S.O., Afolabi, S.O. (2020). Analysis of production scheduling initiatives in the manufacturing systems. International Journal of Mechanical and Production Engineering Research and Development (IJMPERD), 10(3): 1301-1318. https://doi.org/10.24247/ijmperdjun2020113

[15] Suer, G.A., Yang, X., Alhawari, O.I., Santos, J., Vazquez, R. (2012). A genetic algorithm approach for minimizing total tardiness in single machine scheduling. International Journal of Industrial Engineering and Management, 3(3): 163. 

[16] Akande, S., Ajisegiri, G.O. (2021). Single machine multi-criteria scheduling problem: total completion time, maximum lateness, and maximum earliness performance measures. International Journal of Planning and Scheduling, 3(2): 140-159. 

[17] Sunday, A.A., Omolayo, M.I., Remilekun, E.E., Abdulkareem, A., Moses, E.E., Samuel, O.O., Olamma, U.I. (2021). Impact of problems associated with scheduling and capacity planning of a production process–an overview. In E3S Web of Conferences, 309: 01003. https://doi.org/10.1051/e3sconf/202130901003

[18] Bedhief, A.O., Dridi, N. (2020). A genetic algorithm for three-stage hybrid flow shop scheduling problem with dedicated machines. Journal Européen des Systèmes Automatisés, 53(3): 357-368. https://doi.org/10.18280/jesa.530306

[19] Joshi, D., Satpathy, S.K. (2020). Production scheduling of open pit mine using sequential branch-and-cut and longest path algorithm: An application from an African copper mine. Journal Européen des Systèmes Automatisés, 53(5): 629-636. https://doi.org/10.18280/jesa.530505