Scheduling is used to schedule resources in time to finish the tasks. Forecast demand plays a key role to determine the plan for the output.
Methods Used for Scheduling
- Longest Processing Time (LPT): The longest processing time rule orders the jobs in the order of decreasing processing times. Whenever a machine becomes free, the largest job processing starts at the same time. The main aim of this rule is to schedule the longest jobs first so that no large job will remain pending till the end.
- Shortest Processing Time (SPT): This rule arranges the jobs in the increasing order of processing times. Whenever a machine becomes free, the shortest job processing starts on it at the same time.
- Earliest Due Date (EDD): In the single machine environment with ready time set at 0 for all jobs, the earliest due date rule arranges the jobs in increasing order of their due date. EDD arrangement of jobs minimize the maximum lateness, or to minimize the maximum tardiness.
- Minimum Slack Time (MST): The minimum slack time rule arranges the jobs in increasing order of slack. The “urgency” of a job is decided by its slack time. MST rule maximizes the minimum lateness.
- First Come, First Served (FCFS) rule: In case of inventory management, it is treated as First In First Out (FIFO) i.e. first piece of inventory at a storage area is the first one to be used.
- Critical ratio (CR) rule: arranges the jobs in increasing order of their critical ratio.
CR = Due date / Processing Time
If CR>1 The job is ahead of schedule.
If CR<1 The job is behind schedule.
If CR=1 The job is exactly on schedule.
- Slack Time Remaining (STR) rule: It employs that the next job processed is the one that has the least amount of slack time.
Slack = Due date – Processing time
It is the order in which jobs pass through the machines or workstations.
- Number of Machines: It means the service facilities through which a job must pass before it is completed.
- Processing Order: It is the order in which different machines are arranged for completing the job.
- Processing Time: It is the time needed by each job on each machine.
- Idle Time on a Machine: It is the time for which a machine remains idle during the total elapsed time.
- Total Elapsed Time: The time between the start of the first job and completing the last job, is the total elapsed time.
Johnson’s rule (Sequencing of n jobs on 2 machines)
Let, Ai = processing time of ith job on machine 1, Bi = processing time of ith job on machine 2, these problems are solved by Johnson’s rule and steps involved are:
(i) Find out the minimum of Ai and Bi.
(ii) If the minimum is for a particular job on machine A then, perform that job at the start or beginning.
(iii) If the minimum is for a particular job on machine B then, perform that job in the last.
(iv) Strike-off the job which is assigned so that it can’t be considered again.
(v) Continue in the similar manner until all the jobs are assigned.
Example: The above algorithm is illustrated with the following example.
Consider two machines and six jobs flow shop scheduling problem. Using Johnson’s algorithm, obtain the optimal sequence which will minimize the make span.
Step-1: Finding Sequence. Min Processing time of 1 min for job 6 on m1 and for job 3 on m2. Place job 6 first and job 3 at last. Continue this procedure. The sequence obtained is-
Step-2: Using this sequence, the make span for the jobs can be determined by the time in and time out:
Total flow time = 11 + 16 + 24 + 30 + 33 + 36 = 150
Avg. flow time = 150 / 6 = 25
Idle time for M1 = 1 minute.
Idle time for M2 = 1 + 2 = 3 minute.
Make span time of shop = 36 minute.
Sequencing of n jobs on 3 machines (Jackson Rule)
(i) Check (min)M1 ≥ (max)M2
(min)M3 ≥ (max)M2, At least one must satisfy.
(ii) Convert to two machines problem by adding machine 1 and 2,then machine 2 and solve using Johnson’s rule.
Assembly Line Balancing
Assembly line is a special case of product layout in which the operations pertaining to assembly of different parts at few station line (product) layout is useful for high volume, single type of manufacturing activity. The aim of assembly line is to divide total work content into different work station. Such that idle time is minimized utilization is optimized.
Line balancing Terminology
- Work Element (i): Every job is completed by a set of operation and each operation which is performed on the job is called work element.
- Task time (T1): It is the slandered time required to complete work-element.
- Work Stations (ω): It is the specific location on the assembly line where the given amount of work elements are completed within a fixed period of time.
- Station time (Tsi): It is a time required to complete work element assigned in an work-station.
- Total Work Content (Twc): It is time required to complete one set of job. It is given by either the summation of all the station time or the summation of all the elemental task time.
- Cycle Time: It is an amount of time for which a job to be assembled remains in a work station. It is a time gap between two successive product coming out from the assembly line.
Tc ≥ max(Tsi)
- Delay or Idle Time at Station: The difference between cycle time and station time is called the delay or idle time at the station.
Tds = Tc - Tsi
- Balance Delay or Balancing Less (d): It is the measure of the inefficiency of the line.
- Line efficiency:
Where, Tsi = Station time at station
i, n = Total number of stations
TC = Total cycle time.
- Smoothness Index (SI): It is a term used to represent the load distribution between the different work station. Compare to a station consuming maximum time.
Where, (Tsi)max = Maximum station time.
Note: If smoothness index is low, it means line balancing is good.
- Theoretically Minimum Number of Work Stations (Nmin): The minimum number of work stations is defined as the ratio of total work content to the total cycle time.
Method of line balancing- Largest candidate rule steps are:
- List all the element in the decreasing order of their task time
- To assign an element in a work station start form beginning of list moving downward searching feasible element which can be placed in a work station a feasible element is one which satisfy precedence requirement and when that element is placed in the work station the total time of the work station should not exceed the cycle time.
- Strike of the element which is assigned so that it can’t considered again.
- Continue in the similar manner until all the jobs are assigned.
Example: Let us consider the precedence diagram of 13 work elements shown below. The time each work element is at the top of each node. In a tabular form, this precedence diagram is represented as follows.
Total work content = 68 min
Largest work element time = 10 min
Thus, cycle time (TC) must satisfy TC ≥ 10 min
For minimum cycle time of 10 min, number of stations would be 68/10 = 6.8
Therefore, we must take stations lesser than this. Let us select 5 stations design. For 5
stations, the station time should be nearly equal to 68/5 = 13.6 min
List work elements in descending order of their work element.
Here, the final cycle time is the maximum station time which is 16 min.
Balance delay =x 100% = 15%