If a set of n jobs are given which are associated with deadlines and profit is earned and a job is completed by its deadline. These jobs need to be ordered in such a way that there is maximum profit.

Lets take one example. As shown in figure 1.1 an array of jobs is given where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

A simple solution is to generate all subsets of given set of jobs and check individual subset for feasibility of jobs in that subset. Keep track of maximum profit among all feasible subsets. The time complexity of this solution is exponential.We can also solve this problem using greedy method which is more optimal than simple solution.So lets solve this problem via greedy method.

To solve the job sequencing problem via greedy method follow this steps:

1. Sort all jobs in decreasing order of profit.
2. Initialize the result sequence as first job in sorted jobs.
3. Do following for remaining n-1 jobs.
4. If the current job can fit in the current result sequence without missing the deadline, add current job to the result. Else ignore the current job.

As you can see in the figure 1.1 the jobs are already in decreasing order of profit.Here job 1 has the highest profit and the deadline is 3 so set that job between 2–3 as shown in figure 1.2.Job 2 has second highest profit and the deadline is 4 so set that job between 3–4 and do same to all jobs.So the final sequence is J4-J3-J1-J2 and the total profit is 110.

You can prefer the code for this algorithm at https://www.geeksforgeeks.org/job-sequencing-problem.

Time complexity of this solution is O(n²).It can optimized by Disjoint Data Structure.

Hope you like the article.Thank you :)

Traveling Salesman Problem describe the salesman who is travelling between N cities.Salesman knows the route and the cost of cities so he has to find the possible shortest route that visits every city exactly one and returns to the starting city.

As shown in figure 1.1 the salesman is traveling 4 cities and the cost of every city is given.We can solve this problem by brute-force approach and using dynamic programming.In brute-force approach if the number of vertices is N so (N-1)! routes are possible.Instead if brute-force approach dynamic programming is more optimal solution then brute-force approach.Let’s talk about both approaches one by one.

1.Brute-force approach:

Brute-force approach is nothing but trying out all possible solutions one by one though it is time consuming but it is also very easy method to solve TSP problem.

In figure 1.1 four cities are shown as graph and the cost of each edges are also shown there.The salesman can start from any city that he wish but here let us assume that the salesman start from city 1 and travel each cities(nodes) and come back to city 1.

As shown in figure 1.2 let’s take the starting point(city 1) as the root node and other three points(city 2,3,4) as the leaf nodes of the node 1.Do the same thing to every leaf node until you reach the starting point(city 1 or node 1).Then find the total cost of every possible routes and the minimum cost is our solution.

Here in figure 1.2 the minimum cost is 80 so the possible routes are 1–2–4–3–1 and 1–3–4–2–1.Both routes has the same cost 80 so the salesman can travel from any route from that.Now lets talk about dynamic programming approach.

2.Dynamic programming approach:

Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting and ending point of output. For every other vertex i (other than 1), we find the minimum cost path with 1 as the starting point, i as the ending point and all vertices appearing exactly once.

Let the cost of this path be cost(i), the cost of corresponding Cycle would be cost(i) + dist(i, 1) where dist(i, 1) is the distance from i to 1. Finally, we return the minimum of all [cost(i) + dist(i, 1)] values.To calculate cost(i) using Dynamic Programming, we need to have some recursive relation in terms of sub-problems. Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i.

We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset.

If size of S is 2, then S must be {1, i},
 C(S, i) = dist(1, i) 
Else if size of S is greater than 2.
 C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.

For a set of size n, we consider n-2 subsets each of size n-1 such that all subsets don’t have nth in them.
Using the above recurrence relation, we can write dynamic programming based solution. There are at most O(n*2^n) sub-problems, and each one takes linear time to solve. The total running time is therefore O(n^2*2^n). The time complexity is much less than O(n!), but still exponential. Space required is also exponential. So this approach is also infeasible even for slightly higher number of vertices.

For more information you can visit geeksforgeeks.org and https://www.youtube.com/watch?v=XaXsJJh-Q5Y.

Thank you :)