New Algorithm for N-jobs on M-machine Flow Shop Scheduling Problems
Geleta Tadele Mohammed
Department of Mathematics, College of Natural Sciences, Arba Minch University, Arba MInch, Ethiopia
Email address:
To cite this article:
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.
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:
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?
The answer is yes!
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
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.
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:
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.
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:-
= +
=++
=+
=1156+ 942.49+696.96
=2795.45
Similarly, for the sequence of jobs1-3-2 we have,
=+
=++
=+
=2246.76+823.69+121
=3191.45
For the sequence of jobs1-2-3 we have,
=+
=++
=+
=2246.76+484+349.69
=3080.45
For the sequence of jobs 2-1-3 we have,
=+
=++
=+
=1156+1398.76+349.69
=2904.45
For the sequence of jobs3-1-2 we have,
=+
=++
=+
=1656.49+1324.96+121
=3102.45
For the sequence of jobs3-2-1 we have,
=+
=++
=+
=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