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

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.

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

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.

1.png

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.