CIC Season 1 Solutions
Code Industry Challenge Season 1 (an Event by SIME) successfully completed on 21st February 2021. Every participant tried their best to code the most efficient program possible for the given problems. The submissions were judged by the experienced programmers of our society and were examined accordingly. Here, we bring you the sample solutions for Code Industry Challenge season 1. We understand that there can be several approaches to the given problems and some of them might be more efficient than the programs written by members. In case if you were unable to approach the problems then these lines of codes can provide you with a basic idea and maybe you can come well prepared to take the challenge the next season.
Q1: Simplex Method
The linear programming model is given as:
Z= 4x1+5x2+6x3
Subject to the pure constraints
2x1+3x2+2x3≤440,
4x1+3x3≤470,
2x1+5x2≤430,
where x1, x2, x3 ≤ 0
Write a program to convert the above conditions into an opportunity matrix so that the objective function ‘Z’ is maximized. Print all the values of the decision variables and slack variables for which the stated conditions are satisfied. (You can assume all the points form a closed feasible area). You are bound to use Simplex Algorithm to solve this question.
Solution: (C++)
Q2: Transportation Problem
The linear programming model is given as
z=3x1−x2
Subject to the mixed constraints :
2x1+x2≤2,
x1+3x2≥3,
X2≤4 and x1,x2≥0
Write a program to convert the given equations into an opportunity matrix so that the given objective function ‘Z’ is Maximized. Assume whatever slack, artificial variables necessary to satisfy the conditions. Print the value of the objective function and the decision variables. You are bound to use the BIGM algorithm to solve this question.
Solution: (Python)
Q3: Johnson’s Rule/ Sequencing of N jobs on two Machines
Write a program that minimizes the transportation cost of any fed transportation matrix in a way such that the demand and supply are met in the given cells. You have to take plant quantity, distribution center quantity, and transportation cost as input. Your objective is to find the initial feasible solution for a sequence of transporting the units from the plants to the distribution centers and print the transportation cost as your final answer.
Sample Inputs and Outputs :
Enter the number of plants :
3
Enter the number of distribution centers:
4
Enter the transportation cost matrix with the last column as supply and the last row as demand:
The initial feasible solution yields the transportation cost of X.
Solution: (C++)
Assume that the order of jobs for the first and the second machine have to coincide. In fact, since the jobs for the second machine become available after processing them at the first, and if there are several jobs available for the second machine, then the processing time will be equal to the sum of their bi, regardless of their order. Therefore it is only advantageous to send the jobs to the second machine in the same order as we sent them to the first machine.
Consider the order of the jobs, which coincides with their input order 1,2,…,n.
We denote by xi the idle time of the second machine immediately before processing i. Our goal is to minimize the total idle time:
F(x)=∑xi →min
For the first job, we have x1=a1. For the second job, since it gets sent to the machine at the time a1+a2, and the second machine gets free at x1+b1, we have x2=max((a1+a2)−(x1+b1),0).
In general we get the equation:
xk=max(∑i=1kai−∑i=1k−1bi−∑i=1k−1xi,0)
We can now calculate the total idle time F(x). It is claimed that it has the form
F(x)=maxk=1…nKi,
where
Ki=∑i=1kai−∑i=1k−1bi.
This can be easily verified using induction.
We now use the permutation method: we will exchange two neighboring jobs j and j+1 and see how this will change the total idle time.
By the form of the expression of Ki, it is clear that only Kj and Kj+1 change, we denote their new values with K′j and K′j+1.
If this change from of the jobs j and j+1 increased the total idle time, it has to be the case that:
max(Kj,Kj+1)≤max(K′j,K′j+1)
(Switching two jobs might also have no impact at all. The above condition is only a sufficient one, but not a necessary one.)
After removing ∑j+1i=1ai−∑j−1i=1bi from both sides of the inequality, we get:
max(−aj+1,−bj)≤max(−bj+1,−aj)
And after getting rid of the negative signs:
min(aj,bj+1)≤min(bj,aj+1)
Thus we obtained a comparator: by sorting the jobs on it, we obtain an optimal order of the jobs, in which no two jobs can be switched with an improvement of the final time.
However, you can further simplify the sorting, if you look at the comparator from a different angle. The comparator can be interpreted in the following way: If we have the four times (aj,aj+1,bj,bj+1), and the minimum of them is a time corresponding to the first machine, then the corresponding job should be done first. If the minimum time is a time from the second machine, then it should go later. Thus we can sort the jobs by min(ai,bi), and if the processing time of the current job on the first machine is less than the processing time on the second machine, then this job must be done before all the remaining jobs, and otherwise after all remaining tasks.
One way or another, it turns out that by Johnson’s rule we can solve the problem by sorting the jobs, and thus receive a time complexity of O(nlogn).
Code (C++):
Q4: Job Assignment Problem
Write a code that takes the input of a number of jobs with details like Job Name, Job Duration on Machines 1 and 2, Job Profit. To accomplish this task, only two machines are provided and all the jobs are needed to be completed. Each job has to go through the first machine and then the second machine. Code has to tell three optimum sequences of the jobs in terms of -
1. Lowest total elapsed time of both the machines
2. Higher profit jobs are given priority
3. Jobs requiring lesser total time (give priority to machine 1 as a tiebreaker) are completed first
Apart from this, the output should also tell the total elapsed time for each sequence.
Sample Input and Output — Total Number of Job?
3
Enter the name of job 1 — Toy
Enter the production duration of Toyon machine 1 -
5
Enter the production duration of Toyon machine 2–3
Enter the profit per piece of Toy-
18
Enter the name of job 2 -
Ball
Enter the production duration of Ball on machine 1 -
4
Enter the production duration of Ball on machine 2 -
6
Enter the profit per piece of Ball- 12
Enter the name of job 3 -
Gear
Enter the production duration of Gear on machine 1 -
5
Enter the production duration of Gear on machine 2 -
7
Enter the profit per piece of Gear-
40
The sequence for the least elapsed time is Ball, Gear, Toy which takes a total time of 20 minutes.
Sequence for higher profit jobs prioritizes ed is Gear, Toy, Ball which takes a total time of 21 minutes.
Sequence for shorter duration jobs given priority is Toy, Ball, Gear which takes a total time of21 minutes.
Solution: (C++)
Authors -
Soumyarup, IAR Chief, SIME, BIT Mesra, Ranchi, India
Aditya Raj — Event Executor, SIME, BIT Mesra, Ranchi, India
Sameer Singh — Event Chief, SIME, BIT Mesra, Ranchi, India
You may contact the authors for suggestions or criticism (click on their name above to navigate to their Linkedin page).
Authors have full rights to the content of this study, any similarity to any existing idea is just a mere coincidence and should not be considered plagiarism. Authors have done a preliminary study about the existing works done all over the world in this aspect and their idea is built over it successively.
Some images in this report may be subject to copyright, their use in the publication is solely for educational purposes. You can send the request for removal to sime@bitmesra.ac.in
