 Open Access
 Total Downloads : 92
 Authors : Vinod K. T, Joseph O. A, Rajendra Setupathi
 Paper ID : IJERTV6IS040363
 Volume & Issue : Volume 06, Issue 04 (April 2017)
 DOI : http://dx.doi.org/10.17577/IJERTV6IS040363
 Published (First Online): 18042017
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
MultiObjective Comparison of DueDate Assignment Methods in a Dynamic Job Shop with Sequence Dependent setup Time
Vinod K. T,
Department of Mechanical Engineering, Karpagam Academy of Higher Education,
Coimbatore – 641 021.
Joseph O. A,
College of Engineering, Vatakara – 673 105,
Rajendra Setupathi,
Department of Aerospace Engineering, Karpagam Academy of Higher Education,
Coimbatore – 641021.
Abstract This paper focuses on the analysis of due date assignment methods in a dynamic job shop operating in a sequence dependent setup time environment. Five methods are used for assigning the due dates of jobs. Simulation experiments are conducted to evaluate the performance of a typical job shop using measures such as mean flow time, mean tardiness, percentage of tardy jobs, mean setup time and mean flow allowance. Grey relational analysis is used to prioritize the due date assignment methods considering the performance measures simultaneously. The Total Work Content method emerges as the best due date assignment method followed by Dynamic Total Work Content method.
Keywords Dynamic job shop, Sequence dependent set up time, simulation, Grey relational analysis.

INTRODUCTION
Scheduling is defined as timebased allocation of resources to process a set of tasks or jobs. Resources can be machines, facilities, service centers, etc. In a production system, the processing of a job on a machine is called an operation. The order in which a job must visit the machines for processing is called the routing of this job. In a job shop, the machines are usually of a general purpose nature in order to provide the flexibility necessitated by the variation in size, shape, quantity, precision, and type of product. Similar machines are grouped into work centers, and each machine can perform a variety of tasks. A work centre may also function as an assembly area. The job shop scheduling problem consists of determining the order or sequence in which the machines will process the jobs so as to optimize some measure of performance. In a dynamic job shop, orders for jobs to be processed arrive at the system at random points in time.
The following characteristics of a job shop production system make the scheduling problem very challenging [1, 2].

At any time, there is a large number of orders at various stages of completion.

Orders make conflicting demands on facilities and manpower.

Every order differs to some extent. It is difficult, therefore, to predict accurately the time required to complete operations.

There is usually a queue of work at each machine and it is often difficult to determine which order in the queue should have priority.

There are many changes resulting from scrap, rework, machine breakdown, material shortages, engineering changes and rush orders.

Considerable effort is expended in determining the status of orders and in expediting orders through various departments.

Schedules and shop loads are rarely altered due to the very heavy clerical workload required to make the alterations.
In a job shop, a machine may have to be set up before it can process the next operation. This happens, for instance, when tools must be switched offline or when the machine must be cleaned between two operations. During a setup, the machine cannot process any operation. Setup time is encountered in many job shop production systems. Efficient production in such an environment is achieved by minimizing the loss of capacity due to setups and thus explicitly considering the setup times. [3] and [4] emphasize the importance and benefits of incorporating setup times in scheduling research. Effective production in an orderdriven environment is achieved by completing jobs before their due dates, or at least by minimizing the lateness. Due date based scheduling in dynamic manufacturing environments has been studied by several researchers namely, [5], [6], [7], [8], and [9]. However, in these studies, the performance of due date assignment methods has not been analyzed using multi objective methods. Hence, in the present study, a multi objective method known as grey relational analysis is used for comparing the performance of due date assignment methods. This is a significant contribution of the present study.
This paper focuses on the analysis of due date assignment methods in a dynamic job shop operating in a sequence dependent setup time environment. Five methods are used for assigning the due dates of jobs. Simulation experiments are conducted to evaluate the performance of the job shop using measures such as mean flow time, mean tardiness, percentage of tardy jobs, mean setup time and mean flow allowance. Grey relational analysis is used to prioritize the due date
assignment methods considering the performance measures simultaneously.
The rest of the paper is organized as follows. Section 2 provides the description of the dynamic job shop system. Section 3 explains the due date assignment methods. Section 4 presents the scheduling decision rule. Section 5 presents the salient aspects of the simulation model and experiments. Section 6 presents the results and the analyses. Section 7 provides conclusions.


THE JOB SHOP SYSTEM
A simulation model of a dynamic job shop system is developed for investigation. In developing the configuration, the guidelines provided in [10] and [11] are considered. The job shop contains six machines, where each machine is modelled as a single capacity resource. The routing length of jobs varies uniformly from three to six operations. All workstations have an equal probability of being visited and a particular workstation is required at most once in the routing of a job. Processing times follow an exponential distribution with a mean of 30 minutes. The setup time of a job on a machine is generated using an exponential distribution with a mean of 12 minutes. Jobs arrive at the shop according to a Poisson process, resulting in the time between arrivals following exponential distribution. The mean interarrival time of jobs is set such that 85% machine utilization is maintained. It is assumed that due dates are specified exogenously, job releases take place instantaneously, and control is based entirely on the scheduling rule. The job shop described above is similar to those commonly used in studies on due date setting [12].

DUE DATE ASSIGNMENT
In job shop scheduling, due date is the date by which a job is to be completed. Due date assignment decisions are made whenever jobs (customer orders) are received from customers. Good due date assignments are needed in order to maintain high delivery performance (delivery speed and delivery reliability). Generally, due dates can be set: (1) exogenously, or (2) endogenously [13, 14]. In the former case, due dates are decided by independent agencies (sellers, buyers). The present study focuses on the second case, where the due dates are internally set based on the characteristics of the jobs and the shop to improve the delivery performance of
pijm Processing time of job i waiting in the queue of machine m
sijm Setup time of job i waiting in the queue of machine m for operation j
nm Number of machines in the shop
Nst Number of the jobs in the system at time t wj Expected waiting time for operation j
fi Flow allowance for job i
K Due date allowance factor
Basically, the due date Di of a job i is calculated as follows:
Di = Ai + fi (1)
The value of flow allowance fj depend on the due date assignment method. In the present study, the methods used for assigning due dates are described in the following sub secti ons.

Total Work Content Method
This method is known as TWK method. In this method, due date of a job is determined as the sum of the job arrival time and a multiple (due date allowance factor, K) of the total processing time. Since setup times of operations are considered in the present study, the work content of a job includes setup time also. Hence, the average setup time is added to the processing time of operations to obtain the work content of a job. Thus, the due date is assigned as shown below.
Di = Ai + K(pi + ni s) (2) In the present study, K is set equal to 6.

Dynamic Processing plus Waiting Method
In this method proposed by [11], due date of a job is assigned based on the expected waiting time of the job. This method denoted as DPPW is modified in the present study to take into account setup times of operations as follows:
Due Date of a job = Arrival time + total Processing time + total setup time + (number of operations)(expected waiting time of operation)
Thus, the due date of job i is obtained as follows:
job shops. The endogenous due date assignment is especially important when manufacturers need to promise a delivery
ni
i
Di = A + pij
Jt (p + )
S
+
n m
( p + s) (3)
date to customers and it is also useful for better management of shop floor activities. The following are the notations used for describing the due date assignment methods:
Mean arrival rate of jobs
p Mean processing time per operation
s Mean setup time of an operation
g Mean number of operations per job
Di Due date of job i
Ai Arrival time of job i at the shop
j=1

Dynamic Total Work Content Method
It is a modification of the TWK method and it is denoted as DTWK. Here, the due date allowance factor K is determined using the information about the status of the job shop at the time a job arrives at the shop [16, 17]. The dynamic flow allowance factor Kt can be determined as
ni Number of operations in job i
Steady state utilization of the system
pi Total processing time of job i
K =
t
(+)
(4)
To obtain an allowance factor not less than one, the dynamic allowance factor used for due date assignment is set as max (1, Kt), instead of Kt. Accordingly, due date of a job is determined as
ni
Di = Ai + {max (1,Kt )}{( pij + ni * s )} (5)
j=1

Random Flow Allowance Method
This method known as RFA involves modifying the basic method of due date assignment (equation 1) by specifying a random assignment procedure for determining the flow allowance. The flow allowance is determined using the uniform distribution. Thus, the due date of a job is determined as follows
Di = Ai + U (a, b) (6)
where a and b denote the lower and upper limit of the uniform distribution for the flow allowance. In the present study, a and b are set equal to 1000 and 1300 respectively.

Constant Flow Allowance Method
This method known as CFA involves modifying the basic method of due date assignment (equation 1) by specifying a constant flow allowance. Thus, the due date of a job is determined as follows:
Di = Ai + Constant flow allowance (7)
where the constant flow allowance = K (Âµp + Âµs) Âµg. In the present study, K is set equal to 6.


JOB SCHEDULING DECISION RULE
In a dynamic job shop, a scheduling rule is used to select the next job to be processed by a machine when the machine become free after completing an operation. The scheduling rule used in the present research is known as MSRPT: Modified sequence dependent slack per remaining processing time plus shortest processing time. It is a modified version of the combination of slack per remaining processing time and the shortest processing time rule S/RPT + SPT proposed by [18]. This modification is proposed in the present study. In this rule, the operation duedate is set as a multiple of the slack per remaining processing time (S/RPT). Thus, the operation duedate, ODDi j, for operation j of job i is stated as
ODDij = (S/RPT) (pij + sij )
S/RPT = duedate of job current time (remaining process time + remaining average setup time). Thus, MSRPT rule can be expressed as Priority index
= Max {( S/RPT) Ã— (pij + sij), (pij + sij)} where the job with the smallest value of the priority index is selected.

SIMULATION MODEL AND EXPERIMENTATION A discreteevent simulation model of the dynamic job
shop system is developed using the C programming language. The simulation model is subjected to a verification exercise.
The simulation outputs are checked for reasonableness. The performance measures evaluated are mean flow time, mean tardiness, percentage of tardy jobs, mean setup time, and mean flow allowance. In the present research, the five methods used for assigning due dates of jobs lead to five simulation experiments. Ten replications are performed for each experiment. The end of the transient period is identified using the Welch's procedure explained in [19]. The run length of each replication is set equal to the completion of 1500 jobs. The performance measures are evaluated using the simulation outputs after the end of the transient state. For each performance measure, the average value over the ten replications is found out and these results are shown in Table1
TABLE 1. SIMULATION RESULTS
Due Date Method
Mean Flow Time
Mean Tardiness
Percentag e of Tardy jobs
Mean set up time
Mean Flow
Allowan ce
TWK
923.005
11.218
8.118
33.288
945.31
DPPW
1057.637
16.727
8.811
33.03
1059.26
DTWK
891.146
98.034
35.443
34.79
709.37
RFA
1022.408
30.202
15.939
32.872
1118.94
CFA
1026.511
27.909
14.652
32.534
1150

RESULTS AND ANALYSES

tatistical Analysis of Simulation results
The simulation results presented in Table 1 show considerable variations for each performance measure when different due date assignment methods are adopted. Hence, using the simulation results for ten replications, ANOVAF test has been carried out for each performance measure to determine whether the means are significantly different from each other. These results are shown in Table 2. For the performance measure measures such as mean flow time, mean tardiness, percentage of tardy jobs and mean flow allowance, since the pvalue of the Ftest is less than 0.05, there is a statistically significant difference between the mean performance measures from one due date method to another at the 5 % significance level. However, there is no difference in performance among the due date methods for the mean setup time measure.
The analysis of simulation results shows the best performing due date assignment method as follows:

Mean Flow Time: DTWK

Mean Tardiness: TWK

Percentage of Tardy Jobs: TWK

Mean Setup Time: No significant difference among the due date assignment methods

Mean Flow Allowance: DTWK
It is found that the best performing due date assignment method varies over the performanc measures. Hence, grey relational analysis is used to determine the due date assignment method that provides better overall performance considering all the performance measures simultaneously.
TABLE 2 ANOVA RESULTS
Yq can be translated into the comparability sequence Xq = (Xq1, Xq2,, Xqr,, XqR) using the following equation:
Sum of Squares
Degrees of
Freedom
Mean Square
F
p value
Mean Flow Time
Between Groups
210469.227
4
52617.307
3.080
0.025
Within
Groups
768727.632
45
17082.836
Total
979196.859
49
Mean Tardiness
Between
Groups
49295.487
4
12323.872
30.68
0.000
Within Groups
18078.777
45
401.751
Total
67374.264
49
Percentage of Tardy Jobs
Between
Groups
4919.028
4
1229.757
12.977
0.000
Within
Groups
4264.384
45
94.764
Total
9183.412
49
Mean Setup Time
Between
Groups
30.630
4
7.658
1.644
0.180
Within
Groups
209.573
45
4.657
Total
240.203
49
Mean Flow Allowance
Between
Groups
1275608.27
4
318902.07
28.14
0.000
Within Groups
509896.096
45
11331.024
Total
1785504.37
49
Xqr =
Max{Yqr , q 1, 2,…,Q} Yqr
Max{Yqr , q 1, 2,…,Q} Min{Yqr , q 1, 2,…,Q}
for smallerthebetter situations. (8)

Reference sequence definition
If X0r =(x01,x02,, xor, , xoR) = (1,1,,1,…,1) is defined as reference sequence, then GRA aims to find the alternative whose comparability sequence is the closest to the reference sequence.

Grey relational coefficient calculation


Grey relational coefficient is used for determining how much close is xqr to x0r. Based on the reference sequence X0r , after calculating the values of qr, max, min, the grey relational coefficient can be calculated as follows:
The absolute difference of the compared series and the referential series is obtained using the following formula:

Ranking of Due Date Assignment Methods using Grey
Relational Analysis
Grey Relational Analysis (GRA), multiattribute decision making method is used in the present study for ranking the five due date assignment methods under five attributes (performance measures).

Grey Relational Analysis Procedure
The GRA procedure shown in Figure 1 as suggested by Kuo et al. [20] is adopted in the present study. The first step of GRA is grey relational generating. In this step, performance measures of all the alternatives are translated to a comparable manner. A reference sequence or ideal target sequence is defined based on these values. The next step in GRA is gray
qr x0r xqr
The maximum and the minimum difference is found out using the following formula:
max Max{qr , q 1, 2…, Q, r 1, 2,…, R}
min Min{qr , q 1, 2…, Q, r 1, 2,…, R}
The grey relational coefficient j can be expressed as follows:
d
relational coefficient calculation. Based on this gray relational coefficient, gray relational grade is calculated. An
r (xor ,
xqr) min max
qr d max
alternative with highest grade is the best choice of due date assignment method. These steps are explained below.
for q = 1, 2, …, Q , r = 1, 2, …, R (9)
The distinguishing coefficient d is between 0 and 1.
Grey relational generating.
Reference sequence definition.
Grey relational coefficient.
.
Grey Relatio nal Grade
Generally, d is set to 0.5.
d .Grey relational grade calculation
R
Fig. 1 Grey Relational Analysis Procedure

Grey relational sequence generating
Rq wr r
r 1
In equation (10),
for q = 1, 2, …, Q (10)
r is the grey relational coefficient
This step involves translating the performance measures (attributes) into a comparability sequence. If there are R attributes and Q alternatives, the qth alternative can be stated as Yq = (yq1, yq2,, yqr,yqR), where yqr is the value of attribute r of alternative q.
between Xqr and Xor and wr is the weight of the attribute r. This weight will depend on problem or decision makers judgment.
R
wr 1
r 1
The grey relational grade indicates the degree of similarity between the comparability sequence and the reference sequence. On each attribute, the reference sequence represents the best performance that could be achieved by any among comparability sequences. Therefore, if a comparability sequence for an alternative gets the highest grey relational grade with the reference sequence, it means that the comparability sequence is most similar to the reference sequence, and that alternative would be the best choice.


Ranking of due date assignment methods using GRA

In the present study, all the performance measures (attributes) are smallerthebetter category. Statistical analysis of simulation results reveals that there is no significant difference among the due date assignment methods for the mean setup time measure. Hence, mean setup time measure is not considered for the grey relational analysis. Using the remaining four performance measures, the results obtained for grey relational generating are shown in Table 3.
TABLE 3. GREY RELATIONAL GENERATING RESULTS
Due Date Assignment
Method
Mean Flow
Time
Mean Tardiness
Percentage of Tardy
Jobs
Mean Flow
Allowance
TWK
0.80864
1
1
0.46453
DPPW
0
0.93654
0.97464
0.20592
DTWK
1
0
0
1
RFA
0.21159
0.78133
0.71378
0.07047
CFA
0.18695
0.80774
0.76088
0
Based on the reference sequence X0 , after calculating the values of qr, max, and min as described in section 6.2.1, grey relational coefficients are calculated using equation (9). The results obtained are shown in Table 4.
TABLE 4. GREY RELATIONAL COEFFICIENTS
TABLE 5. GREY RELATIONAL GRADES
Due Date Assignment Method
Grey Relatinal Grade
Rank
TWK
0.8015224
1
DPPW
0.6397039
3
DTWK
0.6666667
2
RFA
0.5173817
5
CFA
0.5282201
4
Based on the grey relational grades presented in Table 5, the ranking of the due date assignment methods are as follows:
TWK – DTWK – DPPW – CFA RFA
Thus, TWK provides better performance while considering multiple objectives together.


CONCLUSION
Due date performance is becoming increasingly important in todays competitive environment. In this study, five due date assignment methods are analyzed in a dynamic job shop with the explicit consideration of setup times of jobs on machines. The total work content method for due date assignment emerges as the best method based on the application of the grey relational analysis when multiple objectives are considered. This is followed by the dynamic In the grey relational analysis, weights can be assigned according to managerial decision to give different priorities for performance measures.
The present research has significant implications in the operation and control of a dynamic job shop system. The discreteevent simulation model can be used for investigating the performance of the job shop under various combinations of due date assignment methods and scheduling rules. As a further study, system interruptions namely, breakdowns of machines can be analyzed. Simulation experiments can be conducted under various settings of shop load.
Due Date Assignment Method 
Mean Flow Time 
Mean Tardiness 
Percentage of Tardy Jobs 
Mean Flow Allowance 
TWK 
0.72322 
1 
1 
0.48287 
DPPW 
0.33333 
0.88738 
0.95173 
0.38638 
DTWK 
1 
0.33333 
0.33333 
1 
RFA 
0.38808 
0.6957 
0.63595 
0.34977 
CFA 
0.38079 
0.72228 
0.67648 
0.33333 
The importance of all the four performance measures is taken as equal. Therefore, the weight for each performance measure is assigned as 1/4. Table 5 provides the grey relational grade calculated using equation (10).
REFERENCES

M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems.Third Edition, Springer, 2008.

K. R. Baker, Sequencing rules and duedate assignments in a job shop, Management Science, 30 (1984), 10931104.

Allahverdi, A. and Soroush, H. M. (2008). The significance of reducing setup times/setup costs. European Journal of Operational Research, Volume: 187, Issue: 3, pages: 978984.

Allahverdi, A. (2015). The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, Volume: 246, Issue: 2, pages: 345 378

W.L. Pearn, S. H. Chung, and C. M. Lai, Scheduling integrated circuit assembly operations on die bonder, IEEE Transactions on electronics packaging manufacturing. 30 (2007) 97105.

V. Vinod, and R. Sridharan, Simulation modelling and analysis of duedate assignment methods and scheduling decision rules in a dynamic job shop production system, International Journal of Production Economics. 129, (2011) 127146.

T. Eguchi, K. Nishi, H. Kawai, and T. Murayama, Job shop scheduling to meet due dates with consideration to sequence dependent setup times in a dynamic environment. In ASME/ISCIE 2012 International Symposium on Flexible Automation, American Society of Mechanical Engineers. 365 368.

C. Binchao and T. I. Matis. A flexible dispatching rule for minimizing tardiness in job shop scheduling. International Journal of Production Economics, 141 (2013) 360365.

S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan. Automatic design of scheduling policies for dynamic multiobjective job shop scheduling via cooperative co evolution genetic programming. IEEE Transactions on Evolutionary Computation. (2014) 18, 193208.

Rangsaritratsamee, R., Ferrel, W.G., and Kurtz, M.B. (2004). Dynamic rescheduling that simultaneously considers efficiency and stability. Computers and Industrial Engineering, Volume: 46, Issue: 1, pages: 115.

Hall, N.G. and Posner, M.E. (2001).Generating experimental data for computational testing with machine scheduling applications. Operations Research, Volume: 49, Issue: 7, pages: 854865.

M. ThÃ¼rer, M. Stevenson, C. Silva, M. J. Land, L. D. Fredendall and S. A. Melnyk, Lean control for maketoorder companies: Integrating customer enquiry management and order release. Production and Operations Management, 23(3), (2014) 463476.

T. C. E. Cheng, and M. C. Gupta, Survey of scheduling research involving due date determination decisions. European Journal of Operational Research 38 (1989) 156166.

R. Ramasesh, Dynamic job shop scheduling: a survey of simulation research. Omega, 18 (1990) 4357.

S. T. Enns, A dynamic forecasting model for job shop flow time prediction and tardiness control, International Journal of Production Research, 33 (1995) 1295 – 1312.

T. C. E. Cheng, and J. Jiang, Job shop scheduling for missed due date performance, Computers and Industrial Engineering, 34 (1998)297 – 307.

D. Y. Sha, and C. H. Liu, Using data mining for due date assignment in a dynamic job shop environment, International Journal of Advanced Manufacturing Technology, 25 (2005) 11641174.

E. J. Anderson, and J. C. Nyirenda, Two new rules to minimize tardiness in a job shop. International Journal of Production Research, 28 (1990) 22772292.

A. M. Law, and W. D. Kelton, Simulation modelling and analysis, McGraw Hill Inc. (2001).

Y. Kuo, T. Yang, and GW. Hunag, The use of grey relational analysis in solving multiple attribute decisionmaking problems. Computers & Industrial Engineering, 55 (2008) 80 93.