{"id":25116,"date":"2017-10-15T14:34:21","date_gmt":"2017-10-15T09:04:21","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25116"},"modified":"2017-10-15T14:34:21","modified_gmt":"2017-10-15T09:04:21","slug":"job-sequencing-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/job-sequencing-problem\/","title":{"rendered":"Job Sequencing Problem"},"content":{"rendered":"

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. <\/span>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.<\/p>\n

Examples:<\/strong><\/p>\n

Input: Four Jobs with following deadlines and profits\r\n  JobID    Deadline      Profit\r\n    a        4            20   \r\n    b        1            10\r\n    c        1            40  \r\n    d        1            30\r\nOutput: Following is maximum profit sequence of jobs\r\n        c, a   \r\n\r\n\r\nInput:  Five Jobs with following deadlines and profits\r\n   JobID     Deadline     Profit\r\n     a         2           100\r\n     b         1           19\r\n     c         2           27\r\n     d         1           25\r\n     e         3           15\r\nOutput: Following is maximum profit sequence of jobs\r\n        c, a, e\r\n<\/pre>\n[ad type=\u201dbanner\u201d]\n
We strongly recommend to minimize your browser and try this yourself first.<\/strong><\/p>\n
A Simple Solution<\/strong> 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.<\/p>\n
This is a standard Greedy Algorithm <\/a>problem. Following is algorithm.<\/p>\n
1) Sort all jobs in decreasing order of profit.\r\n2) Initialize the result sequence as first job in sorted jobs.\r\n3) Do following for remaining n-1 jobs\r\n.......a) If the current job can fit in the current result sequence \r\n          without missing the deadline, add current job to the result.\r\n          Else ignore the current job.<\/pre>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Program%20to%20find%20the%20maximum%20profit%20job%20sequence%20from%20a%20given%20array%0A%2F%2F%20of%20jobs%20with%20deadlines%20and%20profits%0A%23include%3Ciostream%3E%0A%23include%3Calgorithm%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20structure%20to%20represent%20a%20job%0Astruct%20Job%0A%7B%0A%20%20%20char%20id%3B%20%20%20%20%20%20%2F%2F%20Job%20Id%0A%20%20%20int%20dead%3B%20%20%20%20%2F%2F%20Deadline%20of%20job%0A%20%20%20int%20profit%3B%20%20%2F%2F%20Profit%20if%20job%20is%20over%20before%20or%20on%20deadline%0A%7D%3B%0A%20%0A%2F%2F%20This%20function%20is%20used%20for%20sorting%20all%20jobs%20according%20to%20profit%0Abool%20comparison(Job%20a%2C%20Job%20b)%0A%7B%0A%20%20%20%20%20return%20(a.profit%20%3E%20b.profit)%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20minimum%20number%20of%20platforms%20reqquired%0Avoid%20printJobScheduling(Job%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Sort%20all%20jobs%20according%20to%20decreasing%20order%20of%20prfit%0A%20%20%20%20sort(arr%2C%20arr%2Bn%2C%20comparison)%3B%0A%20%0A%20%20%20%20int%20result%5Bn%5D%3B%20%2F%2F%20To%20store%20result%20(Sequence%20of%20jobs)%0A%20%20%20%20bool%20slot%5Bn%5D%3B%20%20%2F%2F%20To%20keep%20track%20of%20free%20time%20slots%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20all%20slots%20to%20be%20free%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20slot%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20Iterate%20through%20all%20given%20jobs%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%2F%2F%20Find%20a%20free%20slot%20for%20this%20job%20(Note%20that%20we%20start%0A%20%20%20%20%20%20%20%2F%2F%20from%20the%20last%20possible%20slot)%0A%20%20%20%20%20%20%20for%20(int%20j%3Dmin(n%2C%20arr%5Bi%5D.dead)-1%3B%20j%3E%3D0%3B%20j\u2013)%0A%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%2F%2F%20Free%20slot%20found%0A%20%20%20%20%20%20%20%20%20%20if%20(slot%5Bj%5D%3D%3Dfalse)%0A%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20result%5Bj%5D%20%3D%20i%3B%20%20%2F%2F%20Add%20this%20job%20to%20result%0A%20%20%20%20%20%20%20%20%20%20%20%20%20slot%5Bj%5D%20%3D%20true%3B%20%2F%2F%20Make%20this%20slot%20occupied%0A%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20the%20result%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20if%20(slot%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20arr%5Bresult%5Bi%5D%5D.id%20%3C%3C%20%22%20%22%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20methods%0Aint%20main()%0A%7B%0A%20%20%20%20Job%20arr%5B%5D%20%3D%20%7B%20%7B\u2019a\u2019%2C%202%2C%20100%7D%2C%20%7B\u2019b\u2019%2C%201%2C%2019%7D%2C%20%7B\u2019c\u2019%2C%202%2C%2027%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B\u2019d\u2019%2C%201%2C%2025%7D%2C%20%7B\u2019e\u2019%2C%203%2C%2015%7D%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20cout%20%3C%3C%20%22Following%20is%20maximum%20profit%20sequence%20of%20jobs%5Cn%22%3B%0A%20%20%20%20printJobScheduling(arr%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/h4>\n
Following is maximum profit sequence of jobs\r\nc a e<\/pre>\n
Time Complexity<\/strong> of the above solution is O(n2<\/sup>). It can be optimized using Disjoint Set Data Structure. Please refer below post for details.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Job Sequencing Problem – Greedy Algorithm – Given array of jobs where every job has deadline and associated profit if job is finished before the deadline.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70144],"tags":[71435,71424,71434,71479,71460,71426,71455,71476,71415,71461,71463,71453,71444,71465,71443,71425,71436,71480,71466,71469,71441,71467,71462,71439,71429,71418,71437,71473,71417,71428,71468,71430,71459,71432,71433,71427,71452,71451,71440,71464,71438,71448,71423,71446,71412,71456,71442,71471,71449,71421,71454,71472,71431,71445,71422,71470,71457,71475,71458,71474,71414,71419,71420,71477,71450,71447,71478,71416,71413],"class_list":["post-25116","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-greedy-algorithm","tag-algorithm-for-job-sequencing-with-deadlines","tag-algorithm-jobs","tag-define-job-shop-production","tag-define-sequencing-problem","tag-difference-between-job-scheduling-and-process-scheduling","tag-edd-jobs","tag-example-of-job-shop","tag-example-of-knapsack-problem-using-greedy-method","tag-fcfs-scheduling","tag-how-to-calculate-average-flow-time","tag-job-flow-time","tag-job-m","tag-job-n-shop","tag-job-problems","tag-job-sch","tag-job-scheduling","tag-job-scheduling-algorithm","tag-job-scheduling-algorithm-in-c","tag-job-scheduling-pdf","tag-job-scheduling-problem-example","tag-job-scheduling-problems","tag-job-scheduling-with-deadlines-greedy-algorithm","tag-job-sequence","tag-job-sequence-algorithm","tag-job-sequence-for-n-jobs-in-2-machine","tag-job-sequencing","tag-job-sequencing-algorithm","tag-job-sequencing-in-operation-research","tag-job-sequencing-with-deadlines","tag-job-sequencing-with-deadlines-algorithm","tag-job-sequencing-with-deadlines-example-using-greedy-method","tag-job-sequencing-with-deadlines-program-in-c","tag-job-shop-planning-scheduling-and-control","tag-job-shop-production-ppt","tag-job-shop-scheduling","tag-job-shop-scheduling-excel","tag-job-shop-scheduling-pdf","tag-job-shop-scheduling-ppt","tag-job-shop-scheduling-problem-example","tag-job-shop-scheduling-problem-using-genetic-algorithm","tag-job-shop-scheduling-techniques","tag-job-shopping","tag-jobs-ppt","tag-jssp-jobs","tag-knapsack-problem-example-using-greedy-method","tag-lpt-jobs","tag-n-jobs-2-machines","tag-online-scheduling-algorithms","tag-operations-research-scheduling","tag-operations-scheduling","tag-optimum-solutions-jobs","tag-parallel-job-scheduling","tag-processing-n-jobs-through-2-machines-example","tag-pseudo-code-for-greedy-algorithm","tag-pst-time","tag-scheduling-in-job-shop-type-production","tag-scheduling-optimization-problem","tag-sequence-algorithm","tag-sequence-jobs","tag-sequence-problem-solving","tag-sequencing-model-in-operation-research","tag-sequencing-problem","tag-sequencing-problem-example","tag-single-machine-scheduling","tag-slack-per-operation","tag-time-machine-scheduler","tag-what-is-job-shop-scheduling","tag-what-is-sequence","tag-what-is-sequencing-problem-in-operational-research"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25116","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25116"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25116\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25116"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25116"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}