Definitions [8]
The assignment problem is a special type of problem which deals with the allocation of various resources to various activities on a one-to-one basis.
An unbalanced assignment problem is one in which the number of resources is not equal to the number of activities i.e. the cost matrix of an assignment problem is not a square matrix (no. of rows ≠ no. of columns).
An alternate (multiple) solution exists for an assignment problem when the final assignment matrix contains more than the required number of zeros.
An assignment problem involving restrictions on allocation due to personal, technical, legal or other reasons is called a restricted assignment problem.
A maximization assignment problem is an assignment problem in which the objective is to maximize total profit, revenue, or effectiveness instead of minimizing cost.
This conversion to a minimisation problem can be done in either of the following ways:
- Subtracting all elements of the matrix from the largest element in the matrix, or
- Multiplying all the elements of the matrix by -1.
A sequencing problem is a problem in which the order or sequence of processing a set of jobs on one or more machines is to be determined so as to minimize the total processing time or overall completion time.
It is the time required to complete all the jobs, i.e. the entire task.
or
The total elapsed time is the time between the beginning of the first job on the first machine till the completion of the last job on the last machine.
Idle time is the time when a machine is available but not being used, i.e. the machine is available but is waiting for a job to be processed.
Key Points
The Hungarian Method is an optimisation algorithm that solves an Assignment Problem.
Step 1: Row Reduction
Step 2: Column Reduction
Step 3: Assignment
Step 4: Cover Zeros
Step 5: Create Additional Zeros
- n jobs on 2 machines
-
n jobs on 3 machines
-
2 jobs on m machines
Important Questions [26]
- A job production unit has four jobs A, B, C, D which can be manufactured on each of the four machines P, Q, R and S. The processing cost of each job is given in the following table
- Solve the Following Minimal Assignment Problem and Hence Find the Minimum Value :
- Suggest Optimum Solution to the Following Assignment. Problem, Also Find the Total Minimum Service Time. Service Time ( in Hrs.)
- Solve the Following Minimal Assignment Problem :
- Determine L_92 and L_93, "Given That" L_91 = 97, D_91 = 38 and Q_92 = 27/59
- Solve the Following Minimal Assignment Problem and Hence Find Minimum Time Where '- ' Indicates that Job Cannot Be Assigned to the Machine :
- Solve the Following Maximal Assignment Problem :
- A Departmental Head Has Three Jobs and Four Subordinates. the Subordinates Differ in Their Capabilities and the Jobs Differ in Their Work Contents.
- In a Factory There Are Six Jobs to Be Performed Each of Which Should Go Through Two Machines a and B in the Order a - B
- A job production unit has four jobs P, Q, R, and S which can be manufactured on each of the four machines I, II, III, and IV. The processing cost of each job for each machine
- In an assignment problem, if number of column is greater than number of rows, then a dummy column is added.
- The objective of an assignment problem is to assign ______.
- Choose the correct alternative : The assignment problem is said to be balanced if it is a ______.
- To use the Hungarian method, a profit maximization assignment problem requires ______.
- Three new machines M1, M2, M3 are to be installed in a machine shop. There are four vacant places A, B, C, D. Due to limited space, machine M2 can not be placed at B.
- State whether the following statement is true or false: To convert a maximization-type assignment problem into a minimization problem, the smallest element in the matrix is deducted from all elements
- Four new machines M1, M2, M3 and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D and E available. Because of limited space, machine M2
- A marketing manager has list of salesmen and territories. Considering the travelling cost of the salesmen and the nature of territory, the marketing manager estimates the total of cost per month
- The time interval between starting the first job and completing the last job including the idle time (if any) in a particular order by the given set of machines is called _______.
- A toy manufacturing company produces five types of toys. Each toy has to go through three machines A, B, C in the order ABC. The time required in hours for each process is given in the following table
- There are five jobs, each of which must go through two machines in the order XY. Processing times (in hours) are given below. Determine the sequence for the jobs that will minimize the total elapsed
- Find the sequence that minimizes the total elapsed time to complete the following jobs in the order AB. Find the total elapsed time and idle times for both the machines.
- The time required for printing of four books A, B, C and D is 5, 8, 10 and 7 hours while its data entry requires 7, 4, 3 and 6 hrs respectively.
- If jobs A to D have processing times as 5, 6, 8, 4 on first machine and 4, 7, 9, 10 on second machine then the optimal sequence is ______.
- Six jobs are performed on Machines M1 and M2 respectively. Time in hours taken by each job on each machine is given below: Machines↓\Jobs→ A B C D E F M1 3 12 5 2 9 11 M2 8 10 9 6 3 1
- Five jobs are performed first on machine M1 and then on machine M2. Time taken in hours by each job on each machine is given below: Machines↓\Jobs→ 1 2 3 4 5 M1 6 8 4 5 7 M2 3 7 6 4 16 Determine
