Multi-Objective Comparison of Due-Date Assignment Methods in a Dynamic Job Shop with Sequence Dependent setup Time

Multi-Objective Comparison of Due-Date 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.

1. INTRODUCTION

   Scheduling is defined as time-based 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 off-line 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 order-driven 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.

2. 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].

3. 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.

   1. 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.

   2. 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

   3. 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

   4. 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.

   5. 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.

4. 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 due-date is set as a multiple of the slack per remaining processing time (S/RPT). Thus, the operation due-date, ODDi j, for operation j of job i is stated as

   ODDij = (S/RPT) (pij + sij )

   S/RPT = due-date 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.

5. SIMULATION MODEL AND EXPERIMENTATION A discrete-event 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

6. RESULTS AND ANALYSES

   1. 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, ANOVA-F 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 p-value of the F-test 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 smaller-the-better situations. (8)

        1. 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.

        2. 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:

   1. Ranking of Due Date Assignment Methods using Grey

      Relational Analysis

      Grey Relational Analysis (GRA), multi-attribute decision making method is used in the present study for ranking the five due date assignment methods under five attributes (performance measures).

      1. 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

         1. 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.

      2. Ranking of due date assignment methods using GRA

   In the present study, all the performance measures (attributes) are smaller-the-better 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.

7. 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 discrete-event 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.

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

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

2. K. R. Baker, Sequencing rules and due-date assignments in a job shop, Management Science, 30 (1984), 1093-1104.

3. 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.

4. 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

5. 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) 97-105.

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

7. 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.

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

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

10. 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: 1-15.

11. 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: 854-865.

12. 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) 463-476.

13. 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.

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

15. 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.

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

17. 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) 1164-1174.

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

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

20. Y. Kuo, T. Yang, and G-W. Hunag, The use of grey relational analysis in solving multiple attribute decision-making problems. Computers & Industrial Engineering, 55 (2008) 80- 93.