Applied and Computational Mathematics
Volume 5, Issue 1, February 2016, Pages: 1-9

New Algorithm for N-jobs on M-machine Flow Shop Scheduling Problems

Department of Mathematics, College of Natural Sciences, Arba Minch University, Arba MInch, Ethiopia

Geleta Tadele Mohammed. New Algorithm for N-jobs on M-machine Flow Shop Scheduling Problems. Applied and Computational Mathematics. Vol. 5, No. 1, 2016, pp. 1-9. doi: 10.11648/j.acm.20160501.11

Abstract: Because of flow shop scheduling is one of the most important problems in the area of production management, In this paper, what I have did is that, I have developed a new algorithm for n-jobs m-machine flow shop scheduling problem for special case of n-jobs m-machine flow shop scheduling problem. And also, there is a good self explanatory example to explain the algorithm very well.

Keywords: N-jobs M-machine, Flow Shop Scheduling Problems

1. Introduction and Statement of the Problem

In this paper the -jobs -machines flow shop scheduling problem where processing times of all jobs are deterministic and known before processing is started is studied with the introduction of concepts of optimal value of processing time multiple, assignment of optimal due date and determination of optimal sequence of jobs by minimizing total squared values of lateness. And also the work has been supported by numerical examples and, where  are positive integers.

First, for m=1, the problem was studied by cheng [1]:

All jobs become available for processing at the same time, and they require  units for processing for. Where is the number of jobs.

If  denotes the assigned due date of job  and expressed by

= k , where  is processing time multiple.

Since cost will certainly be incurred whenever a job cannot be completed exactly on its due date, be it early or tardy. It is natural to have minimization of total missed due dates as the objective, for which the total squared values of lateness  is defined as the performance measure.

The subscript  denote the job occupying the  position for an arbitrary sequence of jobs. If   and  respectively denotes the lateness, completion time and assigned due date of the job in position, then

==

This, , where =

Note: Here,

The purpose of square is to consider as we need to minimize both of early and tardiness at the same time.

is the processing time of  position job on the given (only one) machine.

= k , where  is processing time multiple is the approximation of due dates of each jobs. i.e. In this case due dates of each job is not given, so, we have determine them optimally.

= is Completion time of  position job is the sum of all processing time of jobs before  position and  position itself on machine (here we have only one machine).

Hence, cheng [5]obtained an optimal value of processing time multiple as:

After we have obtained the optimum value of  which is, then we can obtain due dates of each jobs. Then, we can use E.D.D (earliest due date) rule to obtain the optimum arrangement or sequence of jobs. This is all about the work done by cheng on n-jobs 1-machine scheduling problem.

Secondly, for m=2, the problem was studied by Ikram [2]:

In short, Ikram’s work was an extension of change [1] work for two machines, with having the following core condition:

It is applied for the minimum processing times of all jobs on the first machine is greater than or equal to the maximum of processing times of all jobs on the second machine.

In this study, I extend the work of change [1] and Ikram [2] to special class of n-jobs m-machine scheduling problem.

Table 1. N-jobs m-machines scheduling problem.

Note that: In the above table and throughout this paper,  represents the processing time of job on machine.

The problem is to determine an optimal value of processing time multiple, assign due date and obtain optimal sequence of jobs which minimizes  (total sum of squared values of lateness).

2. Problem Formulation

2.1. Formulation of Completion Time

Flow time of job  is the time difference between its completion time on the last machine and starting time of it on the first machine. If we consider starting time of the first machine is fixed at zero, then simply flow time is the same for all jobs. But, completion time of job is dependent on sequence of jobs. i.e. Completion time of one job is different from sequence to sequence. A completion time of each job always occurs on the last machine.

Now, the formulation of completion time each job is the following:

Here, as in the case of Ikram [2], the order machines is fixed and it is . Then the corresponding completion time can be calculated as follows in the table below:

Table 2. Completion time of jobs in n-jobs m-machines scheduling problem.

Now, the completion times for jobs 1, 2, and 3 are given below:

Job1: +…++

Job2:+…++

Job3:++…++

And also, the completion time of job done on  position place is given accordingly from the above table as:

, for =1: n

2.2. Problem Formulation and Assumption

In addition to the information we have about this problem above, let us consider n-jobs with deterministic processing times processed on m-machine and the same readiness times, the problem is to find the optimal processing time multiple  for due date assignment problem, the optimal sequence  to minimize the total amount of missed due dates. It is found that is constant for a given job set and  should be in S.P.T (short processing time) rule.

The basic assumptions for the problem are as follows:

1. All processing times are deterministic and known before the starting time of all jobs.

2. The machine cannot simultaneously process two or more jobs at the same time.

3. Jobs Pre-emption is not required.

And also consider the following conditions:

(1.1)

(1.2)

(1.3)

(1.m)

And if  , then the following conditions holds true:

(2.0)

(2.1)

(2.2)

(2.m)

Since all jobs spend more amount of time on the first machine, then = k , where  is processing time multiple. This is because of the condition (1.0) to (1.m).

Let  denotes an arbitrary sequence, and represents jobs occupying  position of. If  represents lateness, completion time and assigned due date oj the job in the , then our objective function is to minimize:

(3)

Since the completion time of the  for any sequence is: , for =1: n and by using = k  equation (3) becomes:

(4)

This is a function of k and to be minimized.

2.3. Optimal Due Date Assignment Procedure

Since the function to be minimized has degree 2, then from calculus concept one can find the value of  that minimize  as follows by using chain rule:

=

This implies that

++++.. . +

Which gives

(5)

According to change [6], , ,,  are constant and independent of the sequence of the jobs.

And also,  is constant and independent of the sequence of the jobs.

Therefore,  is constant and independent of the sequence of the jobs.

Hence, by using the value of , we assign the value of due dates of each to be

=

Theorem (Minimization of  under a certain condition):

Our objective function = can be minimized by applying the rule that job x should be done before job y if the following conditions are satisfied:

(6.1)

(6.2)

(6.3)

(6.4)

(6.m)

Proof:

Since, =, the extending this expression we can obtain that

By having re-arrangement of summation inside the bracket we have,

(7)

From the third term of Equation (10), we obtain:

=+++...+, which is constant and independent of the sequence of the jobs change [1].

And also, the middle term  is constant (because of it is the sum of square quantity) and independent of sequence of the jobs.

Now, the remaining thing to prove is that can be minimized by applying the conditions given above in the theorem?

Let  be a sequence of jobs in which job x and y are arranged in a position k and k+1 respectively, and  be a sequence of the jobs in which job x and y are arranged in apposition of k+1 and k respectively.

Let

(8)

And

(9)

Now, by expanding equation (8), we obtain

=  + +++...++++

(10)

) =++++...+++++...

(11)

Now,  =

(12)

Then by simplifying equation (12) we get

=

=+++…++++++…+

=

=

Now, if

,

Then.

Thus, the interchanging of job  and  reduces the value of.

Hence, job  should be done before job.

Therefore, the conditions stated in the above theorem are satisfied.

Now, by repeatedly applying the above rule,  can be minimized by arranging jobs depending on their processing time on the first machine as S.P.T rule.

In this study, we developed the following flowchart for the above theorem and show how  is minimized.

2.4. Flow Chart

Figure 1. Flow chart of how to Get Optimal Sequence.

3. Algorithms to Get Optimal Sequence

Step 1: Verify that the conditions given from (1.0)-(1.m) and (2.0) – (2.m). If a1l of these conditions holds true proceed to the next step. Else stop.

Step 2: Determine the values of  using by the formula (5).

Step 3: By using shortest processing time rule on the first machine  determine the optimal sequence of jobs.

Step 4: Finally, find  for the obtained optimal sequences of jobs.

Example

For the following 3-jobs 3-machine flow shop scheduling problem, find the optimal sequence of jobs such that is minimum.

Table 3. 3-jobs 3-machine flow shop scheduling problem.

Solution:

Here, what we have to do is that, according to the above algorithm, we have to find:-

Due-dates of each job.

An optimal sequence.

Step 1:

Clearly,

And also, let say job 1 is x and job 2 is y.

Then, = (12) (8) =96

(5)

(7)

(3)

This implies that

Therefore, all conditions for step 1 are satisfied.

Step 2:

Since,

(5)

Then, because of our problem is for n=3=m,  becomes,

Now, by using this values of  we can assign the due dates of each job as follows:

Table 4. Assign the due dates of each job by using this values of .

Step 3:

As indicated in the above algorithm, we arrange jobs as per shortest processing time rule on machine 1(). And also, the same result we obtain, if we arrange jobs by earliest due date rule.

Therefore, by using both of them (one of them is enough), we obtain the optimal sequence of jobs 2-3-1.

Step 4:

Determination of . Here, is listed in the following table for all possible sequences of jobs we have.

Table 5.  for all possible sequences of jobs.

Note that,  is calculated by

=, because of n=m=3 for our problem, then it becomes

=

=++

For instance, for the sequence of jobs2-3-1:-

Table 6. The sequence of jobs2-3-1.

= +

=++

=+

=1156+ 942.49+696.96

=2795.45

Similarly, for the sequence of jobs1-3-2 we have,

Table 7. The sequence of jobs1-3-2.

=+

=++

=+

=2246.76+823.69+121

=3191.45

For the sequence of jobs1-2-3 we have,

Table 8. The sequence of jobs1-2-3.

=+

=++

=+

=2246.76+484+349.69

=3080.45

For the sequence of jobs 2-1-3 we have,

Table 9. The sequence of jobs 2-1-3.

=+

=++

=+

=1156+1398.76+349.69

=2904.45

For the sequence of jobs3-1-2 we have,

Table 10. The sequence of jobs3-1-2.

=+

=++

=+

=1656.49+1324.96+121

=3102.45

For the sequence of jobs3-2-1 we have,

Table 11. The sequence of jobs3-2-1.

=+

=++

=+

=1656.49+529+696.96

=2882.45

Now, from the above table the optimal sequence of the given jobs is 2-3-1 with  = 2795.45.

This completes our example.

Recommendation

Here what I have as recommendation is that one can do one or both of the following:

I. One can develop a program for this algorithm accordingly, in order to handle the problem for large values of n and m.

II. One can extend the condition I have used in my work for in order to handle large size of problem as much as possible.

References

1. Chenge, T.C.E.,"Optimal due date determination and scheduling of n- jobs on a single machine", Journal of the Operation Research society 35, pp.433-437, 1984.
2. Ikram, M.,"A note on minimization of lateness Cost Function and Determination of Optimal Due –date in two machine problem," Pure Applied Mathematika sciences, Vol.XXIII, 1-2, March 1986.
3. Johnson,S.M."Optimal two and three stage production schedules with setup times included." Naval Research Logistics Quarterly, Vol I, 61-68, 1954.
4. Jackson, J.R.,"An extension of Johnson’s results on lot scheduling", Naval Research Logistics Quarterly, Vol 3, pp.201-2003,1956.
5. Ibrahim,M.A.,"Algorithms for Sequencing and Scheduling," Industrial Engineering Department, College of Engineering, King saud University, Riyadh, Saudi Arabia.
6. Osman, M.R., Ismail, N., Zairian, M.R.M, Yusuf, R.M., Sapuan, S.M."sheet metal Fabrication Scheduling Using Selective Performance Measure and priority Dispatching Rule," International Journal of Engineering and Technology, Vol.1 (1), pp.74-83, 2004.
7. Taylor,F.W.,"Shop Management", Harper And Bros, New York, 1911.
8. Herrmann, Jeffrey.W "A history of production Scheduling" in Handbook of Production Scheduling, Springer, New York,2006.
9. Dudek,R.A., S.S. Panwalkar, and M.L. Smith,"The lessons for flow shop scheduling Research," Operation Research, Vol 40(1), pp.7-13, 1993.
10. Conway, R.W., Maxwell, W.L., and Miller, L.W."Theory of Scheduling," Addison-Wesley Publishing Company, Massachusetts, 1967.
11. Miloš Šeda "Mathematical Models of Flow Shop and Job Shop Scheduling Problems", International Journal of Applied Mathematics and Computer Sciences Volume 4 Number 4.
12. Kerem Bu¨lbu¨l, Philip Kaminsky, Candace Yano," Flow Shop Scheduling with Earliness, Tardiness, and Intermediate Inventory Holding Costs", Industrial Engineering and Operations Research, University of California, Berkeley, California 94720-1777.
13. Mircea ANCĂU,"on solving flow shop scheduling problems" THE PUBLISHING HOUSE PROCEEDINGS OF THE ROMANIAN ACADEMY, Series A, OF THE ROMANIAN ACADEMY Volume 13, Number 1/2012, pp. 71–79.

 Contents 1. 2. 2.1. 2.2. 2.3. 2.4. 3.
Article Tools