Greedy Algorithms Programming, Data Structures and Algorithms English Malayalam

Greedy AlgorithmsYouTube↗ IA↗(long shot)
People & Blogs 936 views 4 likes 0 dislikes 30 Jan 2018

Programming, Data Structures and Algorithms 451 subscribers N/A YouTube↗

So, today's lecture is about greedy algorithms, and specifically we will be studying one algorithm

ഇന്നത്തെ പ്രഭാഷണം ഗ്രീഡി അൽഗോരിതങ്ങളെക്കുറിച്ചാണ് (greedy algorithm), ജോബ് ഷെഡ്യൂളിംഗിനായി (job scheduling) ഒരു അൽഗോരിതം (algorithm) പഠിക്കും. ആദ്യം ഗ്രീഡി അൽ‌ഗോരിതംസിന്റെ (greedy algorithm) പ്രചോദനം വളരെ ലളിതമായ ഒരു

for a problem call job scheduling. The initial part of the presentation will present you

ഉദാഹരണം വഴി അവതരിപ്പിക്കും. ഇനിപ്പറയുന്ന പ്രശ്നം നമുക്ക് പരിഗണിക്കാം, ഉദാഹരണത്തിന് നമുക്ക്

the motivation for greedy algorithms by a very simple algorithm, very simple example.

832 രൂപ ഉണ്ടെന്ന് കണക്കാക്കാം, കൂടാതെ കഴിയുന്നത്ര കുറച്ച് നോട്ടുകളും നാണയങ്ങളും

The example is the change making example. So, let us consider the following problem

ഉപയോഗിച്ച് 832 രൂപ സൂക്ഷിക്കണം. ഇന്ത്യൻ കറൻസിയിൽ രൂപയുടെ 9 ഡിനോമിനേഷനുകൾ

where for an example let us consider we have 832 rupees, and using as few notes and coins as possible, we should keep 832 rupees let us say in our purse. In general we know the there are 9 denominations of rupees in the Indian currency. So, let us call these denominations

(denomination) ഉണ്ടെന്ന് നമുക്കറിയാം. നമുക്ക് ഈ വിഭാഗങ്ങളെ d 1 മുതൽ d 9 വരെ വിളിക്കാം, അവ 1000, 500, 100, 50, 20, 10, 5, 2, 1 എന്നിവയാണ്.

d 1 to d 9, indeed they take the values from 1000, 500, 100, 50, 20, 10 , 5, 2 and 1.

സ്വാഭാവികമായും നമ്മൾ‌ കഴിയുന്നത്ര കുറച്ച് നോട്ടുകളും നാണയങ്ങളും വഹിക്കാൻ താൽ‌പ്പര്യപ്പെടുന്നു, പൊതുവായ ചോദ്യം ഇതാണ് M രൂപ തന്നിട്ടുണ്ടെങ്കിൽ 9 വേരിയബിളുകൾ‌ (variable)

Naturally we wish to carry as few notes and coins as possible and the generic question

തിരിച്ചറിയുക; പോസിറ്റീവ് ഇന്റിജെർ വേരിയബിളുകൾ

is given M rupees identify 9 variables; these are integer valued variables, positive integer

(positive integer variable). M രൂപയെ x1d1, x2d2,...x9d9 ആയി കണക്കാക്കാം, ഉദാഹരണത്തിന്, 832 എന്ന് എഴുതാം ഒരു

valued variables. Such that M rupees can be written as a sum of x 1 times, the first denomination

500 രൂപയും മൂന്ന് 100 രൂപയും ഒരു 20 രൂപ,

d 1, x 2 times the second denomination d 2 so on up to x 9 times the ninth denomination

ഒരു 10 രൂപ, ഒരു 2 രൂപ നാണയം. ഈ പ്രശ്നം

d 9. For example, 832 can be written as one 500 rupees plus three 100 rupees one 20 rupees,

പരിഹരിക്കുന്നതിന് പൊതുവായി നിങ്ങൾക്ക് ഇവിടെ സ്വാഭാവിക സമീപനമുണ്ട്. ആവർത്തനപരമായി നിലവിലുള്ള തുകയേക്കാൾ ചെറുതായ ഏറ്റവും വലിയ ഡിനോമിനേഷൻ (denomination) തിരഞ്ഞെടുക്കുന്നു.

one 10 rupee, and one 2 rupee coin. In general do you have a natural approach here to solve

നമുക്ക് ഇത് ഉദാഹരണമായി നിരീക്ഷിക്കാം 832 ഏറ്റവും വലിയ വിഭാഗത്തിലെ നിലവിലെ തുക 500 രൂപ

this problem. The natural approach seems to be that iteratively we select the large largest

നോട്ടാണ്. അതിനാൽ, ഞങ്ങൾ 500 രൂപ എടുക്കുന്നു, ബാക്കി 332 ആണ്. ഇപ്പോൾ 332 നെക്കാൾ ചെറിയ

denomination, which is available which is smaller than the current amount. Let us observe

ഏറ്റവും വലിയ വിഭാഗങ്ങൾ 100 രൂപ നോട്ടാണ്, സ്വാഭാവികമായും

this by us the example itself 832 is the current amount in the largest denomination which is available to us is a 500 rupee note. So, we pick up 500 rupees and the balance that is to be expressed is 332. Now 332 the smallest the largest denominations smaller than 332

ഞങ്ങൾ നൂറ് തിരഞ്ഞെടുക്കുന്നു, ബാലൻസ് 232, ഏറ്റവും ചെറിയ വിഭാഗങ്ങൾ വലുതാണ്, ഈ തുകയേക്കാൾ ചെറുത് 100 ആണ്, അങ്ങനെ. അതിനാൽ, ഞങ്ങൾ മൂന്ന് തവണ 100 രൂപ തിരഞ്ഞെടുക്കുന്നു. അതിനുശേഷം 20 രൂപ നോട്ടിൽ

is a 100 rupee note, naturally we pick three times 100 th, we pick 100 once then the balance

തിരഞ്ഞെടുക്കുന്നു, കാരണം എക്സ്പ്രസ് (express) ചെയ്യേണ്ട ബാലൻസ് 32 രൂപയാണ്. ലഭ്യമായ

is 232, the smallest denomination large, the largest denominations smaller than this amount

ഏറ്റവും വലിയ ഡിനോമിനേഷൻ (denomination) തിരഞ്ഞെടുക്കുന്നുവെന്നതാണ് പൊതുവായ ആശയം, അത് നിലവിലെ തുകയേക്കാൾ

is another 100, and so on. So, we pick three times 300 rupees. Then we pick at 20 rupee

ചെറുതാണ്. ഇത് എല്ലായ്പ്പോഴും പ്രവർത്തിക്കുമോ, ഇത് രസകരമായ ഒരു ചോദ്യമാണ്. ഒരു നിശ്ചിത

note, because a balance that is to be express is 32 rupees and so on. So, the generic idea

സെറ്റ് (set) ഡിനോമിനേഷനുകളുമായി (denomination) ഞങ്ങൾ ഇന്ത്യൻ കറൻസിയിൽ ചെയ്തുവെന്ന് നിരീക്ഷിക്കുക, ചില

seems to be that we select the largest denomination that is available, such that it is smaller than the current amount that we need to express. Does this always work independent of the denominations, this is an interesting question. Observe that

കറൻസിയിലെ ഏതെങ്കിലും ഡിനോമിനേഷനുകൾക്ക് (denomination) ഈ സമീപനം പ്രവർത്തിക്കുമോ എന്ന് നമുക്ക് നോക്കാം. കറൻസി ഉള്ള ഒരു രാജ്യം യഥാക്രമം 1, 3, 4 എന്നിങ്ങനെയാണെന്നും മറ്റൊരു ഡിനോമിനേഷൻ (denomination) ഇല്ലെന്നും

we did our exercise with the Indian currency with a fix set of denominations, let us imagine whether this approach will work for any arbitrary set of denominations in some currency. Let

നമുക്ക് അനുമാനിക്കാം. നമ്മുടെ സ്വാഭാവിക ജനറിക് (generic) സമീപനം ഒപ്റ്റിമൽ (optimal) പരിഹാരം നൽകുമോ, നമുക്ക് നോക്കാം. 6 ന്റെ ഏറ്റവും

us assume that there is a country with currency whose denominations are 1, 3 and 4 respectively, and there is no other denomination. Would our natural generic approach yield the optimum

ലളിതമായ കേസ് നമുക്ക് പരിഗണിക്കാം. പൊതുവായ സമീപനം പ്രയോഗിച്ചാൽ 6 നെക്കാൾ ചെറിയ ഡിനോമിനേഷൻ (denomination) തിരഞ്ഞെടുക്കും, അതിനാൽ ഞങ്ങൾ 4 തിരഞ്ഞെടുക്കും,

solution, let us see. Let us consider the simplest case of 6. So, if you apply our generic

അതിനുശേഷം നമുക്ക് 2 ശേഷിക്കുന്നു, അത് 1+1 ആയി പ്രകടിപ്പിക്കാം .പ്ലസ് 1.

approach we will pick the largest denominations smaller than the amount which is 6, therefore

അതിനാൽ, ഞങ്ങളുടെ പരിഹാരം 4 +1 +1 ആയിരിക്കും,

we will pick 4 after which we are left with 2, which can be expressed as 1 plus 1.

മറുവശത്ത്, ഈ കറൻസിയിൽ സാധ്യമായ ഏറ്റവും മികച്ച ഡിനോമിനേഷൻ (denomination), 6 ന്റെ ഏറ്റവും

So, our solution would be 4 plus 1 plus 1, on the other hand it is clear in this very simple example that the best denomination possible, the best representation of 6 possible

മികച്ച പ്രാതിനിധ്യം 3+3 ആണെന്ന് വളരെ ലളിതമായ ഈ ഉദാഹരണത്തിൽ വ്യക്തമാണ്. ഈ ജനറിക് അൽ‌ഗോരിതം (algorithm) വളരെ സ്വാഭാവിക സമീപനമാണെന്ന് തോന്നുന്നു,

in this currency is 3 plus 3. Therefore, it is clear that this generic algorithm which

ഇത് എല്ലാ കറൻസികൾ‌ക്കും പ്രവർത്തിക്കുന്നില്ല, ഇത് വിഭാഗങ്ങളെ ആശ്രയിച്ചിരിക്കുന്നു. ഇത് ഇന്ത്യൻ കറൻസിക്ക്

seems to be a very natural approach, it does not work for all currencies, it depends only the seems to depend on the denominations. At definite exercise which we will not address

വേണ്ടി പ്രവർത്തിക്കുന്നുണ്ടോ, അങ്ങനെയാണെങ്കിൽ എന്തുകൊണ്ട്? ഇത് നിങ്ങൾ ചെയ്തു നോക്കുക. ഗ്രീഡി അൽ‌ഗോരിതംസിന്റെ (greedy algorithm) ആശയം ഇതാണ്.

in this class is does this work for the Indian currency in if so why does it? We will not

ഞങ്ങൾ പ്രാദേശികമായി ഏറ്റവും മികച്ച തിരഞ്ഞെടുപ്പ് തിരഞ്ഞെടുക്കുന്നു. ഒരു നിശ്ചിത തുക

addresses, but this is a left as an exercise for the interested student.

നൽകിയാൽ, നിലവിലെ തുക കവിയാതെ സാധ്യമായ ഏറ്റവും വലിയ ഡിനോമിനേഷൻ (denomination) ഞങ്ങൾ തിരഞ്ഞെടുക്കുന്നു.

This takes as to this whole idea of greedy algorithms. So, observe that our algorithmic

ഇത് ഒരു അർത്ഥത്തിൽ അത്യാഗ്രഹപരമായ ഒരു തിരഞ്ഞെടുപ്പാണ്, ഇത് ഒടുവിൽ ഒരു ഉത്തമ

approach is a greedy approach, we choose the locally best possible choice. So, given a

പരിഹാരത്തിലേക്ക് നയിക്കുമെന്ന് പ്രതീക്ഷിക്കുന്നു. നമ്മൾ കണ്ടതുപോലെ ഇത് എല്ലാ കറൻസികൾക്കും

certain amount, we choose the largest possible denomination without exceeding the current amount. So, this is in some sense a greedy choice hoping that this will eventually lead

പ്രവർത്തിക്കുന്നില്ല. അതിനാൽ, ഗ്രീഡി അൽ‌ഗോരിതംസിന് (greedy algorithm) അനുയോജ്യമായ ഒരു ഘടന ഉണ്ടായിരിക്കണം. എന്താണ് ഒപ്റ്റിമൽ സബ്സ്ട്രക്ചർ (optimal

to a optimal solution. As we have seen it does not work for all currencies. So, therefore,

substructure)? പ്രശ്‌നത്തിന് അനുയോജ്യമായ പരിഹാരത്തിന്റെ അസ്തിത്വം ഉറപ്പ് നൽകാൻ ഞങ്ങൾക്ക്

greedy algorithms should have an optimal substructure. What is an optimal substructure? We should

കഴിയണം, അതായത് ഈ ഒപ്റ്റിമൽ (optimal) പരിഹാരത്തിൽ ഉപ പ്രശ്‌നങ്ങൾക്കും അനുയോജ്യമായ പരിഹാരങ്ങൾ

be able to guarantee the existence of an optimal solution to the problem, such that this optimal

അടങ്ങിയിരിക്കുന്നു. ഇത് വളരെ പ്രധാനപ്പെട്ട ഒരു ആശയമാണ്, നിങ്ങൾക്ക് ഒരു പ്രശ്നമുണ്ട് കൂടാതെ നിങ്ങൾക്ക് പ്രശ്നത്തിന്റെ

solution also contains optimal solutions to the sub problems. This is a very important

ഉപ പ്രശ്നങ്ങളും ഉണ്ട്. ഏത് നെറ്റ്‌വർക്കിലെയും

concept, you have a problem and you also have sub problems of the problem. This is best

ഷോർട്ടസ്റ് പാത്ത് പ്രോബ്ലം ഇതാണ്. നെറ്റ്‌വർക്ക് അൺഡയറക്ടഡ് ആണ്, ഒരു ഉറവിടവും

illustrated by the shortest path problem in any network. Let us assume that the network

ലക്ഷ്യസ്ഥാനവും തമ്മിലുള്ള ഏറ്റവും ചെറിയ പാത്ത് പ്രശ്നം നമുക്ക് നോക്കാം.

is undirected, and let us sink of the shortest path problem between a source and destination.

ഉറവിടത്തിനും ലക്ഷ്യസ്ഥാനത്തിനുമിടയിൽ നിങ്ങൾ ഏറ്റവും ചെറിയ പാത തിരഞ്ഞെടുക്കുകയാണെങ്കിൽ, കൂടാതെ ഏറ്റവും ചെറിയ

Observe that if you pick any shortest path between the source and destination, and if

പാതയിൽ ഏതെങ്കിലും ജോഡി വെർട്ടീസുകൾ (vertices) തിരഞ്ഞെടുക്കുകയാണെങ്കിൽ, ഹ്രസ്വമായ പാതയിൽ

you pick any pair of vertices on the shortest path not necessarily, so source and destination,

ഇന്റർമീഡിയറ്റ് പോയിന്റുകൾക്കിടയിൽ (intermediate point) ഒരു ഹ്രസ്വ പാത അടങ്ങിയിരിക്കുന്നു.

it is clear that the shortest path contains a shortest path between the intermediate points.

ഹ്രസ്വമായ പാതയുടെ വളരെ സ്വാഭാവിക പ്രോപ്പർട്ടി (property) ആണിത്. ഇതാണ് ഒപ്റ്റിമൽ സബ്സ്ട്രക്ചർ

So, very natural property of shortest path. So, this is the optimal substructure. Observe

(optimal substructure). ഇവിടെ അൽ‌ഗോരിതം (algorithm) ചോയ്‌സുകളൊന്നുമില്ലെന്ന് (choice) നിരീക്ഷിക്കുക, ഇത് ഒരു ഒപ്റ്റിമൽ

that no algorithmic choices here, it is just a property of an optimum solution. The greedy

സൊല്യൂഷന്റെ (optimal solution) പ്രോപ്പർട്ടി (property) മാത്രമാണ്. ഗ്രീഡി ചോയ്‌സ് പ്രോപ്പർട്ടി

choice property is an algorithmic choice, it is says that you can obtain a globally

(greedy choice property) ഒരു അൽഗോരിതം ചോയ്‌സാണ് (algorithm choice),

optimum solution by making locally optimal choices. We have seen this example of the

ലോക്കൽ ഒപ്റ്റിമൽ ചോയ്‌സുകൾ (local optimal choice) നടത്തി നിങ്ങൾക്ക് ഗ്ലോബൽ ഒപ്റ്റിമൽ

change making problem, and we wonder whether it has a greedy choice property.

(global optimal) പരിഹാരം നേടാനാകുമെന്ന് പറയുന്നു.

We have already observed that if the denomination is denominations are 1, 3 and 4 respectively, if you take an optimum solution. Let us take the optimum solution for 6 in this example, which is 3 plus 3, note that every sub set of notes is the optimum change for it some.

ഡിനോമിനേഷനുകൾ (denomination) യഥാക്രമം 1, 3, 4 എന്നിവയാണെന്ന് ഞങ്ങൾ‌ ഇതിനകം നിരീക്ഷിച്ചു. ഈ ഉദാഹരണത്തിൽ 6-നുള്ള ഒപ്റ്റിമൽ സൊല്യൂഷൻ (optimal solution) നമുക്ക് എടുക്കാം, അത് 3+3 ആണ്, നോട്ടുകളുടെ (note) ഓരോ സെറ്റും (set)

അതിനുള്ള ഏറ്റവും അനുയോജ്യമായ ചേഞ്ച്

So, in this case every sub set is just the note 3 itself, which is optimum change for itself. So, this is easy. The greedy choice on the other hand is not satisfied as we have

(change) ആണ്. ഈ സാഹചര്യത്തിൽ ഓരോ സബ്സെറ്റും (subset) 3 ആണ്, അത് സ്വയം ഒപ്റ്റിമൽ ചേഞ്ച് (optimal change) ആണ്.

already seen we will select 4, then we selected one followed by a one in this turned out to

ഇത് എളുപ്പമാണ്. ഗ്രീഡി (greedy) തിരഞ്ഞെടുപ്പ് തൃപ്തികരമല്ല, കാരണം 4 തിരഞ്ഞെടുക്കുമെന്ന്

be suboptimal. So, we repeat this exercise would the greedy choice work for the Indian currency. Indeed in this slide we have observed that the optimal substructures seems to work

ഇതിനകം കണ്ടുകഴിഞ്ഞു, തുടർന്ന് 1 തിരഞ്ഞെടുത്തു, ഇത് സബ്ഒപ്ടിമൽ (sub optimal) ആണ്. ഇന്ത്യൻ കറൻസിയുടെ ഗ്രീഡി (greedy) തിരഞ്ഞെടുപ്പ്

for any currency. However, like I said earlier we will not address it in this presentation, because the problem

പ്രവർത്തിക്കും. ഈ സ്ലൈഡിൽ (slide), ഒപ്റ്റിമൽ സബ്സ്ട്രക്ചറുകൾ (optimal substructure) ഏതെങ്കിലും കറൻസിക്ക് വേണ്ടി പ്രവർത്തിക്കുന്നതായി

was not as easy as it seems, it is very easy to state it, but it is very closely related to problems, which after many years of research have not yielded to give efficient yielded

ഞങ്ങൾ നിരീക്ഷിച്ചു. എന്നിരുന്നാലും, ഞാൻ നേരത്തെ പറഞ്ഞതുപോലെ ഈ അവതരണത്തിൽ ഞങ്ങൾ ഇത് അഭിസംബോധന ചെയ്യില്ല, കാരണം പ്രശ്നം എളുപ്പമല്ലായിരുന്നു, അത് പ്രസ്താവിക്കുന്നത്

to efficient algorithms for example, there is a problem called the knapsack problem.

വളരെ എളുപ്പമാണ്, നിരവധി വർഷത്തെ ഗവേഷണങ്ങൾക്ക്

It does not have efficient algorithms to date it is believed not to have efficient algorithms,

ശേഷം കാര്യക്ഷമമായ അൽ‌ഗോരിതം കണ്ടുപിടിച്ചിട്ടില്ല. ഉദാഹരണത്തിന്, നാപ് സാക്ക് (knapsack) പ്രശ്നം

there is also the optimum denomination problem which is actually a problem face by currency designers. Where the question is what is the best denomination to ensure that for every

എന്ന് വിളിക്കുന്ന ഒരു പ്രശ്നമുണ്ട്. ഇന്നുവരെ കാര്യക്ഷമമായ അൽ‌ഗോരിതം (algorithm) ഇല്ലെന്ന് വിശ്വസിക്കപ്പെടുന്നു, കറൻസി ഡിസൈനർ‌മാർ (currency designer) നേരിടുന്ന ഒരു പ്രശ്നമാണ് ഒപ്റ്റിമൽ

number you get the smallest possible change by our approach.

ഡിനോമിനേഷൻ‌ (optimal denomination) പ്രശ്‌നവും.

So, therefore, let us ask as slightly different question, other problems for which greedy

ഓരോ സംഖ്യയ്ക്കും സാധ്യമായ ഏറ്റവും ചെറിയ ചേഞ്ച് (chenge) നിങ്ങൾക്ക് ലഭിക്കുന്നുവെന്ന്

algorithms result in optimum solutions, this is the focus. The change making example was

ഉറപ്പാക്കാനുള്ള ഏറ്റവും മികച്ച ഡിനോമിനേഷൻ (denomination) ഏതാണ് എന്നതാണ് ചോദ്യം.

a natural example to visualize the greedy algorithm scenario.

അല്പം വ്യത്യസ്തമായ ഒരു ചോദ്യമായി നമുക്ക് ചോദിക്കാം, ഗ്രീഡി അൽ‌ഗോരിതം (greedy algorithm)

Let us look at the problem, which is very well in call, very well known as a scheduling

ഒപ്റ്റിമൽ (optimal) പരിഹാരങ്ങൾക്ക് കാരണമാകുന്ന മറ്റ്

problem. There is a single machine, and there are n jobs; each of these jobs can run only

പ്രശ്നങ്ങൾ, ഇതാണ് ഫോക്കസ് (focus). ഗ്രീഡി അൽ‌ഗോരിതം (greedy algorithm) ദൃശ്യവൽക്കരിക്കുന്നതിനുള്ള

on this single machine, and should be run on the single machine, and the jobs are already

ഒരു സ്വാഭാവിക ഉദാഹരണമാണ് രൂപ ചേഞ്ച് (change) ചെയ്യുന്ന ഉദാഹരണം.

known to have running times t 1, t 2, to t n respectively. In other words the job j i takes t i units of time on the machine M. They aim is the following, the aim is identify

നമുക്ക് ഷെഡ്യൂളിംഗ് (scheduling) eപ്രശ്നം നോക്കാം. ഒരൊറ്റ മെഷീൻ (machine) ഉണ്ട്, ഒപ്പം n ജോലികളും ഉണ്ട്; ഈ ജോലികൾ ഓരോന്നും ഈ സിംഗിൾ മെഷീനിൽ

a schedule of jobs, that is the order in which the jobs will execute in the machine. So,

(machine) മാത്രമേ പ്രവർത്തിപ്പിക്കാൻ കഴിയൂ, കൂടാതെ ജോലികൾക്ക്

that we minimize the sum of the completion times.

യഥാക്രമം t1, t2, tn വരെ പ്രവർത്തി സമയം ഉണ്ടെന്ന്

Now minimizing the sum of completion times can also be thought of as minimizing the average of the all the completion times, it is very important for the student note that this average

അറിയാം. മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, ജോലി ji മെഷീനിൽ t i സമയം എടുക്കുന്നു. ജോലികളുടെ ഒരു ഷെഡ്യൂൾ (schedule) തിരിച്ചറിയുകയാണ്

duration, this is not the average duration which is a fixed number, it is the average

ലക്ഷ്യം, അതാണ് മെഷീനിൽ (machine) ജോലികൾ നടപ്പിലാക്കുന്ന

time that a machine spends waiting for the average time a jobs spends waiting for a machine,

ക്രമം. പൂർ‌ത്തിയാക്കുന്ന സമയങ്ങളുടെ ആകെത്തുക കുറയ്‌ക്കുന്ന ക്രമം കണ്ടെത്തണം.. ഇപ്പോൾ പൂർ‌ത്തിയാക്കുന്ന സമയങ്ങളുടെ ആകെത്തുക

and then the time that it spends on the machine itself, one once to minimize this quantity.

കുറയ്‌ക്കുന്നത്‌ പൂർ‌ത്തിയാക്കുന്ന എല്ലാ സമയങ്ങളുടെയും ശരാശരി കുറയ്‌ക്കുന്നതായി കണക്കാക്കാം, ഈ ശരാശരി ദൈർ‌ഘ്യം, ഒരു മെഷീനിൽ

Therefore, the goal of this exercise is to find an ordering of jobs to execute on a machine.

(machine) എക്സിക്യൂട്ട് (execute) ചെയ്യുന്നതിനുള്ള ജോലികളുടെ ക്രമം കണ്ടെത്തുക എന്നതാണ്

So, that we minimizes the sum of completion times.

ഈ വ്യായാമത്തിന്റെ ലക്ഷ്യം. പൂർ‌ത്തിയാക്കുന്ന

Let us do the small example; there are 4 jobs; job one takes 15 units of time, job 2 takes 8 units of time, job 3 takes 3 units of time, job 4 takes 10 units of time. The total duration that the machine will spend executing these jobs, clearly is 15 plus 8 23 units plus 3

സമയങ്ങളുടെ ആകെത്തുക കുറയ്‌ക്കുന്നു. നമുക്ക് ചെറിയ ഉദാഹരണം ചെയ്യാം; 4 ജോലികൾ ഉണ്ട്; ജോലി1 15 യൂണിറ്റ് (unit) സമയവും, ജോലി 2 ന് 8 യൂണിറ്റ് (unit) സമയവും, ജോലി 3 ന് 3 യൂണിറ്റ്

26 plus 10 36 unit of time. Therefore, the average duration on the machine seems to be

(unit) സമയവും, ജോലി 4 ന് 10 യൂണിറ്റ് (unit) സമയവും എടുക്കും. ഈ ജോലികൾ നിർവഹിക്കുന്നതിന്

9 units of time is 9 units of time. However, the completion time is a completely different entity as shown by this graphic. Consider the first schedule in this graphic, where job 1, job 2, job 3, and job 4 are scheduled;

മെഷീൻ (machine) ചെലവഴിക്കുന്ന ആകെ ദൈർഘ്യം 15 + 8 +23+ 3 + 10 = 36 യൂണിറ്റ് (unit) സമയവുമാണ്. അതിനാൽ, മെഷീനിലെ (machine) ശരാശരി ദൈർഘ്യം 9 യൂണിറ്റ്

job 1 finishes after 15 units of time on the machine, job 2 then finishes after 8 units

(unit) സമയമാണ്. എന്നിരുന്നാലും, ഈ ഗ്രാഫിക് (graphic) കാണിക്കുന്നതുപോലെ

of time, therefore the completion time of job 2 is 23, job 3 which actually spends a

പൂർത്തീകരണ സമയം തികച്ചും വ്യത്യസ്തമായ ഒരു എന്റിറ്റിയാണ് (entity). ജോലി 1, ജോലി 2,

least amount of time on the machine, which is 3 units of time completes at time instant

ജോലി 3, ജോലി 4 എന്നിവ ഷെഡ്യൂൾ (schedule) ചെയ്‌തിരിക്കുന്ന

26 and job 4 completes a 36 as a time . Therefore, now if you average these completion times, we see that the average is 25, that is 100 units of time is spent, there is sum of the

ആദ്യ ഷെഡ്യൂൾ (schedule) പരിഗണിക്കുക; ജോലി 1 മെഷീനിൽ (machine) 15 യൂണിറ്റ് (unit) സമയത്തിന് ശേഷം പൂർത്തിയാക്കുന്നു, ജോലി 2 പിന്നീട് 8 യൂണിറ്റ് (unit) സമയത്തിന് ശേഷം പൂർത്തിയാക്കുന്നു,

completion times is 100. On the other hand, let us consider the second schedule, where

അതിനാൽ ജോലി 2 ന്റെ പൂർത്തീകരണ സമയം

interestingly the shortest job is schedule first, then the second shortest job, then

23 ആണ്, ജോലി 3 ഇത് മെഷീനിൽ (machine) ഏറ്റവും കുറഞ്ഞ

the third shortest job, then the fourth shortest job which is the order, job 3, job 2, job

സമയം ചെലവഴിക്കുന്നു, അതായത് 3 യൂണിറ്റുകൾ

4, and job 1. Now observe that the average completion time is 17.75 units of time, which is smaller significantly than the schedule where the jobs where scheduled according to the order in which they were presented in the input. So, now do you have an algorithm

(unit) സമയം തൽക്ഷണം 26 ഉം ജോലി 4 36 ഉം പൂർത്തിയാക്കുന്നു. ഇപ്പോൾ ഈ പൂർത്തീകരണ സമയങ്ങളുടെ ശരാശരി 25 ആണ്. അതായത് 100 യൂണിറ്റ് (unit) സമയം ചെലവഴിച്ചു, പൂർത്തീകരണ സമയങ്ങളുടെ ആകെത്തുക 100 ആണ്. മറുവശത്ത്,

നമുക്ക് രണ്ടാമത്തെ ഷെഡ്യൂൾ (schedule) പരിഗണിക്കാം,

here to minimize a sum of completion times. To do this let us write down the formula for

എവിടെ രസകരമെന്നു പറയട്ടെ, ഏറ്റവും ചെറിയ ജോലി ആദ്യം ഷെഡ്യൂൾ (schedule), തുടർന്ന്

the sum of the completion times.

രണ്ടാമത്തെ ഹ്രസ്വ ജോലി, മൂന്നാമത്തെ

Before that let us look at the schedule. Let us look at properties of the schedule before

ഹ്രസ്വ ജോലി, നാലാമത്തെ ഹ്രസ്വ ജോലി. ഇപ്പോൾ ശരാശരി പൂർത്തീകരണ സമയം നിരീക്ഷിക്കുക

we do the calculation for the sum of the completion times, let us look at a property of a schedule.

സമയം 17.75 യൂണിറ്റ് (unit)ആണ്, ഇത് ഇൻപുട്ടിൽ (input) അവതരിപ്പിച്ച ക്രമമനുസരിച്ച് ജോലികൾ ഷെഡ്യൂൾ (schedule) ചെയ്ത ഷെഡ്യൂളിനേക്കാൾ

One observation that we can make is that if we taken arbitrary schedule and exchange the

(schedule) വളരെ ചെറുതാണ്. അതിനാൽ, പൂർ‌ത്തിയാക്കുന്ന

position of a shortest job in particular let us say the first shortest job in the schedule

സമയങ്ങൾ‌ കുറയ്‌ക്കുന്നതിന് ഒരു അൽ‌ഗോരിതം (algorithm) ഉണ്ടോ? ഇത് ചെയ്യുന്നതിന്, പൂർ‌ത്തിയാക്കുന്ന

with the first job in the schedule. So, let us look at our example in the first job, if we exchange the jobs j 3 with a first job observe that we will get a better schedule,

സമയങ്ങളുടെ ആകെത്തുക ഫോർമുല (formula) എഴുതാം. അതിനുമുമ്പ് നമുക്ക് ഷെഡ്യൂൾ (schedule) നോക്കാം. പൂർ‌ത്തിയാക്കുന്ന സമയങ്ങളുടെ ആകെത്തുക കണക്കാക്കുന്നതിനുമുമ്പ് ഷെഡ്യൂളിന്റെ (schedule)

then the one that was given first. So, if we assume that there is always an optimal

സവിശേഷതകൾ‌ നോക്കാം, ഒരു ഷെഡ്യൂളിന്റെ (schedule) ഒരു പ്രോപ്പർ‌ട്ടി (property) നോക്കാം. ഞങ്ങൾ

schedule where the first job is a shortest job, then it is clear that there is a very

അനിയന്ത്രിതമായ ഷെഡ്യൂൾ (schedule) എടുക്കുകയും ഒരു ഹ്രസ്വ ജോലിയുടെ സ്ഥാനം കൈമാറ്റം

interesting optimal substructure that if you remove the shortest job, the remaining schedule for the remaining jobs is indeed optimal. In other words, if you take a optimal schedule in which the shortest job is schedule first by removing that shortest job. The remaining

ചെയ്യുകയും ചെയ്താൽ, ഷെഡ്യൂളിലെ (schedule) ആദ്യത്തെ ഹ്രസ്വ ജോലി പറയാം. ആദ്യത്തെ ജോലിയിലെ നമ്മുടെ ഉദാഹരണം നോക്കാം, j 3 ജോലികൾ ആദ്യ ജോലി ഉപയോഗിച്ച് കൈമാറ്റം

ചെയ്താൽ നമുക്ക് ഒരു മികച്ച ഷെഡ്യൂൾ

schedule is indeed an optimum schedule for the remaining N-1. Of course, we do not know

(schedule) ലഭിക്കും, തുടർന്ന് ആദ്യം നൽകിയ ഒന്ന്.

if there is an optimal schedule which contains the shortest job first, that is what we are

അതിനാൽ, ആദ്യത്തെ ജോലി ഏറ്റവും ഹ്രസ്വമായ ജോലിയാണെങ്കിൽ ഒരു ഒപ്റ്റിമൽ ഷെഡ്യൂൾ

going to study now by writing down a formula for this sum of the completion times.

(optimal schedule) എല്ലായ്പ്പോഴും ഉണ്ട്, വളരെ രസകരമായ

So, to do this let us assume that there is a schedule which we refer to using the Greek letter sigma, and let us assume that sigma 1 denote the first job and sigma N denote

ഒപ്റ്റിമൽ സബ്സ്ട്രക്ചർ (optimal substruture) ഉണ്ടെന്ന് വ്യക്തമാണ്, നിങ്ങൾ ഹ്രസ്വമായ ജോലി നീക്കംചെയ്യുകയാണെങ്കിൽ, ശേഷിക്കുന്ന ജോലികൾക്കുള്ള ശേഷിക്കുന്ന ഷെഡ്യൂൾ (schedule) തീർച്ചയായും ഒപ്റ്റിമൽ (optimal) ആയിരിക്കും.

the Nth job in the sequence. Now, let us look at the sum of the completion times, the sum of the completion times is return as a first formula where there are N jobs, and let us

മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, നിങ്ങൾ ഏറ്റവും അനുയോജ്യമായ ജോലി നീക്കംചെയ്ത് ഏറ്റവും ചെറിയ ജോലി ആദ്യം ഷെഡ്യൂൾ (schedule) ചെയ്യുന്ന ഒപ്റ്റിമൽ ഷെഡ്യൂൾ (optimal schedule) എടുക്കുകയാണെങ്കിൽ.

observe that the time taken by the first job, that is the job sigma of 1 that will be counted

ശേഷിക്കുന്ന ഷെഡ്യൂൾ (schedule) തീർച്ചയായും ശേഷിക്കുന്ന N-1 നുള്ള ഏറ്റവും അനുയോജ്യമായ ഷെഡ്യൂളാണ് (schedule). ആദ്യം ഏറ്റവും കുറഞ്ഞ

it will delay every sub sequent job, apart from using t sigma of 1 units of time on the machine. In the first job that we schedule which is sigma of 1 takes t sigma of one units

ജോലി ഉൾക്കൊള്ളുന്ന ഒപ്റ്റിമൽ ഷെഡ്യൂൾ (optimal schedule) ഉണ്ടോ എന്ന് ഞങ്ങൾക്ക് അറിയില്ല, അതാണ് പൂർത്തീകരണ സമയത്തിന്റെ ഈ തുകയ്ക്ക്

of time on the machine, not only there it also delays remaining n minus 1 jobs by t

ഒരു ഫോർമുല (formula) എഴുതിക്കൊണ്ട് ഇപ്പോൾ പഠിക്കാൻ

sigma of 1 units of time, same for t sigma of 2 it is a second job - it is completion

പോകുന്നത്. ഇത് ചെയ്യുന്നതിന് ഗ്രീക്ക് അക്ഷരം σ സൂചിപ്പിക്കുന്ന ഒരു ഷെഡ്യൂൾ (schedule)

time is the time there it spent waiting for the machine which is t sigma of 1 plus a time that it spends processing on the machine which is t sigma of 2. In general if you look at the whole expression for the sum of completion times, the formula is given there, it is N

ഉണ്ടെന്ന് നമുക്ക് അനുമാനിക്കാം, കൂടാതെ (1) ആദ്യ ജോലിയെ സൂചിപ്പിക്കുന്നുവെന്നും σ(n) സീക്വൻസിലെ (sequence) nth ജോലിയെ സൂചിപ്പിക്കുന്നുവെന്നും കരുതുക. ഇപ്പോൾ, പൂർ‌ത്തിയാക്കുന്ന സമയങ്ങളുടെ ആകെത്തുക നോക്കാം, ആദ്യത്തെ

ജോലി എടുത്ത സമയം, അതാണ് σ(1) കണക്കാക്കുന്നത്

terms in the summation and there are n minus k plus 1 copies of t sigma of k.

മെഷീനിൽ (machine) 1 യൂണിറ്റ് (unit) സമയത്തിന്റെ tσ(1) ഉപയോഗിക്കുന്നതിനുപുറമെ, ഓരോ തുടർച്ചയായ ജോലിയും വൈകും. ഷെഡ്യൂൾ (schedule) ചെയ്യുന്ന ആദ്യ ജോലി

And that is explained in the equality there which says that the completion time is t sigma of 1 plus the completion time of the second job which is t sigma of 1 plus t sigma of

മെഷീനിൽ (machine) tσ(1) സമയം എടുക്കുന്നു, മാത്രമല്ല അവിടെ ശേഷിക്കുന്ന n-1 ജോലികൾ tσ(1) യൂണിറ്റ്

2 plus a completion of time of the third job which is t sigma of 1 plus t sigma of 2 plus t sigma of 3 and so on up to the completion time of the nth job which is t sigma of 1

(unit)സമയത്തിന്റെ കാലതാമസം വരുത്തുന്നു, രണ്ടാമത്തെ ജോലി പൂർത്തിയാകുന്ന സമയമാണ് tσ(2), അത് മെഷീനായി (machine) കാത്തിരിക്കുന്ന സമയമാണ്, കൂടാതെ

plus t sigma of 2 up to t sigma of N. If i rewrite the summation by adding and subtracting

മെഷീനിൽ (machine) പ്രോസസ്സിംഗ് (processing) ചെലവഴിക്കുന്ന tσ(2) സമയവുമാണ്. പൊതുവേ നിങ്ങൾ നോക്കുകയാണെങ്കിൽ പൂർ‌ത്തിയാക്കുന്ന സമയത്തിന്റെ ആകെത്തുക,

a few terms, we get the third term in the whole equality sequence which is viewed as

സമവാക്യം അവിടെ നൽകിയിരിക്കുന്നു. അവിടെയുള്ള സമത്വത്തിൽ ഇത് വിശദീകരിച്ചിരിക്കുന്നു, ഇത് പൂർത്തിയാക്കുന്ന സമയം tσ(1) രണ്ടാമത്തെ ജോലിയുടെ പൂർത്തീകരണ

2 summations. Observe that the first summation which is N plus 1 multiplied by summation

സമയവും tσ(1)+tσ(2) ഉം മൂന്നാമത്തെ ജോലിയുടെ സമയം tσ(1)+tσ(2)+tσ(3) ഉം അങ്ങനെ ഒൻപതാമത്തെ ജോലിയുടെ പൂർത്തീകരണ

of the processing times of the N jobs, that is the first term minus summation k times

സമയം tσ(1) +tσ(2) +tσ(3) ...+tσ(n). ഞാൻ സംഗ്രഹം മാറ്റിയെഴുതുകയാണെങ്കിൽ കുറച്ച് നിബന്ധനകൾ കുറച്ചുകൊണ്ട്, സമവാക്യ

t sigma of k that is the kth job the processing time of the kth job. Observe that the first term is independent of the schedule and the second term really be is very dependent of the schedule. Observe that this sum of completion times is indeed valid for every schedule sigma,

ശ്രേണിയിലെ മൂന്നാമത്തെ പദം നമുക്ക് 2 സംഗ്രഹങ്ങളായി കാണുന്നു. N ജോലികളുടെ പ്രോസസ്സിംഗ് (processing) സമയങ്ങളുടെ സംഗ്രഹത്താൽ N+1 ആയ ആദ്യത്തെ സംഗ്രഹം ഗുണിതമാകുന്നത് നിരീക്ഷിക്കുക, k+tσ(k)

ആണ് k ന്റെ ആദ്യത്തെ പ്രോസസ്സിംഗ് (processing)

this is a very important thing. So, what we have done in this slide is to write down the closed form expression for the sum of completion times, for a arbitrary

സമയം. ആദ്യ ടേം (term) ഷെഡ്യൂളിൽ (schedule) നിന്ന് സ്വതന്ത്രമാണെന്നും രണ്ടാമത്തെ ടേം (term)

schedule which we have call sigma. And then we have observe that this sum of completion

ശരിക്കും ഷെഡ്യൂളിനെ (schedule) ആശ്രയിച്ചിരിക്കുന്നു. ഓരോ ഷെഡ്യൂൾ‌ (schedule) സിഗ്മയ്‌ക്കും (sigma)

times can be viewed as 2 summations; one that is independent of the schedule itself and the second one which is dependent of the schedule. And there is a subtraction term there, therefore as a second term increases the total cost becomes smaller. So, let us see what makes

ഈ പൂർ‌ണ്ണ സമയങ്ങൾ‌ സാധുതയുള്ളതാണ്. ഈ സ്ലൈഡിൽ‌ (slide) ഞങ്ങൾ‌ ചെയ്‌തത്, പൂർ‌ത്തിയാക്കുന്ന സമയങ്ങളുടെ ആകെത്തുകയ്ക്കുള്ള ക്ലോസ്‌ഡ്‌ ഫോം എക്‌സ്‌പ്രഷൻ (closed form expression), ഷെഡ്യൂളിനായി (schedule) എഴുതുക എന്നതാണ്.

പൂർ‌ത്തിയാക്കുന്ന സമയങ്ങളുടെ ആകെത്തുകയെ

a second term to decrease? Let us see what makes the second term to actually increase,

2 സംഗ്രഹങ്ങളായി കാണാൻ‌ കഴിയും. ഒന്ന് ഷെഡ്യൂളിൽ (schedule) നിന്ന് സ്വതന്ത്രവും രണ്ടാമത്തേത്

and therefore reduces sum of completion terms completion times.

ഷെഡ്യൂളിനെ (schedule) ആശ്രയിച്ചുള്ളതുമാണ്. അവിടെ ഒരു കുറയ്ക്കൽ പദം ഉണ്ട്, രണ്ടാമത്തെ

So, let us see a property of an optimal schedule. So, let us imagine a schedule sigma, and let

ടേം (term) കൂടുന്നതിനനുസരിച്ച് മൊത്തം ചെലവ് ചെറുതായിത്തീരുന്നു. രണ്ടാമത്തെ പദം കുറയുന്നത് എന്താണെന്ന് നോക്കാം.

us assume that there is an index x which is more than an index y, but the processing time for the job which is scheduled as sigma of x is smaller than the processing time of the

രണ്ടാമത്തെ ടേം (term) യഥാർത്ഥത്തിൽ വർദ്ധിപ്പിക്കുന്നതിന് കാരണമാകുന്നത് എന്താണെന്ന് നമുക്ക് നോക്കാം, ഒപ്റ്റിമൽ ഷെഡ്യൂളിന്റെ (optimal schedule) ഒരു പ്രോപ്പർട്ടി (property) നമുക്ക് നോക്കാം. നമുക്ക് ഒരു ഷെഡ്യൂൾ

job schedules sigma of y. In other words y is scheduled sigma of y is later than sigma of x, but the processing time of sigma of y is larger than the processing time of sigma of x. So, let us try the most natural thing, let us exchange the positions of the 2 jobs.

(schedule) സിഗ്മയെ സങ്കൽപ്പിക്കാം, ഒരു സൂചിക y യേക്കാൾ കൂടുതലുള്ള ഒരു സൂചിക x ഉണ്ടെന്ന് നമുക്ക് അനുമാനിക്കാം, എന്നാൽ x ന്റെ സിഗ്മയായി ഷെഡ്യൂൾ (schedule) ചെയ്തിട്ടുള്ള ജോലിയുടെ പ്രോസസ്സിംഗ്

(processing) സമയം ജോലിയുടെ പ്രോസസ്സിംഗ് (processing)

So, in other words, what do we do we exchange the position of the job in position sigma of y with the position of the job sigma of x. And let us see how would changes the duration.

സമയത്തേക്കാൾ ചെറുതാണ് y യുടെ സിഗ്മ ഷെഡ്യൂളുകൾ (schedule). മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, y യുടെ സിഗ്മ x ന്റെ സിഗ്മയേക്കാൾ പിന്നീടുള്ളതാണ്, എന്നാൽ y ന്റെ സിഗ്മയുടെ പ്രോസസ്സിംഗ് (processing)

So, let us see what happens, we should just go back to the formula and observe that the

സമയം x ന്റെ സിഗ്മയുടെ പ്രോസസ്സിംഗ് (processing) സമയത്തേക്കാൾ വലുതാണ്. നമുക്ക് ഏറ്റവും

terms just change by modifying the multipliers appropriately. In other words, we have written

സ്വാഭാവികമായത് പരീക്ഷിക്കാം, നമുക്ക് 2 ജോലികളുടെ സ്ഥാനങ്ങൾ കൈമാറാം. മറ്റൊരു

down in inequality which says that x times t of sigma of x plus y times t of sigma of

വിധത്തിൽ പറഞ്ഞാൽ, y ന്റെ സ്ഥാന സിഗ്മയിലെ ജോലിയുടെ സ്ഥാനം x ന്റെ തൊഴിൽ സിഗ്മയുടെ

y, this is the contribution to the second term by these 2 jobs, and then we may exchange

സ്ഥാനവുമായി ഞങ്ങൾ എന്താണ് ചെയ്യുന്നത്? ദൈർഘ്യം എങ്ങനെ മാറ്റുമെന്ന് നോക്കാം. എന്താണ്

the position of these 2 jobs. The contribution just becomes y times t of sigma of x plus

സംഭവിക്കുന്നതെന്ന് നമുക്ക് നോക്കാം, ഞങ്ങൾ ഫോർമുലയിലേക്ക് (formula) മടങ്ങുകയും ഗുണിതങ്ങൾ

x times t of sigma of y. We now show that x times t of sigma of x plus

ഉചിതമായി പരിഷ്‌ക്കരിക്കുന്നതിലൂടെ നിബന്ധനകൾ മാറുകയും ചെയ്യുന്നു. മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, അസമത്വത്തിൽ ഞങ്ങൾ എഴുതിയിട്ടുണ്ട്, ഇത് x ന്റെ x മടങ്ങ് സിഗ്മയും y ന്റെ സിഗ്മയുടെ

y times t of sigma of y is smaller than the summation after swapping it, that is y times

y തവണയും ആണ്, ഇത് ഈ 2 ജോലികളുടെ രണ്ടാമത്തെ

t of sigma of x plus x times t of sigma of y. This is very easy to see by the following sequence of expressions by just rewriting x times t x times t subscript sigma of x plus

ടേമിനുള്ള (term) സംഭാവനയാണ്, തുടർന്ന് നമുക്ക് സ്ഥാനം കൈമാറ്റം ചെയ്യാം ഈ 2 ജോലികൾ. y*tσ(x)+xtσ(y) ആയി മാറുന്നു. ഞങ്ങൾ ഇപ്പോൾ കാണിക്കുന്നത് x*tσ(x) + y*tσ(x) സ്വാപ്പ് (swap) ചെയ്തതിനുശേഷമുള്ള

y times t subscript sigma of y, this sequence of expressions actually shows that the exchange

സംഗ്രഹത്തേക്കാൾ ചെറുതാണ്, അതായത് y*tσ(x)+xtσ(y). ഇനിപ്പറയുന്ന എക്സ്പ്രഷനുകളുടെ (expression) ക്രമം ഉപയോഗിച്ച് ഇത് കാണാൻ വളരെ എളുപ്പമാണ്,

actually increases the value of the second term.

എക്സ്ചേഞ്ച് (exchange) യഥാർത്ഥത്തിൽ രണ്ടാമത്തെ ടേമിന്റെ (term) മൂല്യം വർദ്ധിപ്പിക്കുന്നുവെന്ന് കാണിക്കുന്നു. . ഇതിന്റെ അനന്തരഫലമായി,

As a consequence of this, it is clear that if we start off with an arbitrary ordering and if we identify a pair of jobs at sigma of x and sigma of y with the property that sigma of y is later than sigma of x, and the time taken by the job schedule that sigma

ഞങ്ങൾ‌ ഒരു ഓർ‌ഡറിംഗ് (ordering) ഉപയോഗിച്ച് ആരംഭിക്കുകയും σ(x) σ(y) ഒരു ജോഡി ജോലികൾ തിരിച്ചറിയുകയും ചെയ്താൽ‌, σ(y) σ(x) യേക്കാൾ പിന്നീടുള്ള സ്വത്താണെന്നും, σ(y) ന്റെ ഷെഡ്യൂൾ (schedule)

of y is more than the time taken by the job scheduled at sigma of x. If we exchange these

ചെയ്തിട്ടുള്ള ജോലി എടുക്കുന്ന സമയത്തേക്കാൾകൂടുതലാണ് σ(y) യുടെ ജോലി ഷെഡ്യൂൾ (schedule) എടുത്ത സമയം. ഈ 2 ജോലികൾ കൈമാറ്റം ചെയ്യുകയാണെങ്കിൽ.

2 jobs. The contribution to the second term in the sum of completion times reduces, and therefore we have a new schedule whose sum of completion times is strictly smaller.

പൂർ‌ത്തിയാക്കുന്ന സമയങ്ങളുടെ ആകെത്തുകയിലെ രണ്ടാമത്തെ ടേമിനുള്ള (term) സംഭാവന കുറയുന്നു, ഒരു പുതിയ ഷെഡ്യൂൾ‌ (schedule) ഉണ്ട്, പൂർ‌ത്തിയാകുന്ന സമയങ്ങളുടെ എണ്ണം ചെറുതാണ്.

ഗ്രീഡി അൽ‌ഗോരിതം (greedy algorithm) വളരെ ലളിതമായ

Consequently the greedy algorithm is a very simple algorithm it says that from the given

ഒരു അൽ‌ഗോരിതം (algorithm) ആണ്, തന്നിരിക്കുന്ന

set of jobs schedule the shortest duration job first. That it is indeed an optimal algorithm follows from our analysis of the completion time that this schedule has a smaller completion

സെറ്റ് (set) ജോലികളിൽ നിന്ന് ആദ്യം ഹ്രസ്വകാല ജോലിയുടെ ഷെഡ്യൂൾ (schedule) എന്ന് അത് പറയുന്നു. ഈ ഷെഡ്യൂളിന് (schedule) മറ്റേതൊരു ഷെഡ്യൂളിനേക്കാളും

time than any other schedule.

(schedule) ചെറിയ പൂർ‌ത്തിയാക്കൽ‌ സമയമുണ്ട്.