Computer Science

Greedy Algorithm-task scheduling problem

Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.

Thread Solved

•

Join Date: Jan 2008

Posts: 16

Reputation: lulusweety is an unknown quantity at this point

Solved Threads: 0

lulusweety lulusweety is offline

Offline

Newbie Poster

Greedy Algorithm-task scheduling problem

Jan 24th, 2008

The problem of scheduling unit-time tasks with deadlines and penalities for a single processor has following inputs
S={a1,a2,...,an} of n unit-time task. A unit-time task requires exactly 1 unit of time to complete
deadlines d1,d2,...,dn, 1<=di<=n
penalities w1,w2,...,wn. A penality wi is incurred if task ai is not finished by time di, and no penality if task finishes at deadline

The problem is to find a schedule for S that minimizes the total penalty incurred for missed deadlines

I got a problem regarding this . It is as follows

ai 1 2 3 4 5 6 7
di 4 2 4 3 1 4 6
wi 70 60 50 40 30 20 10

The solution to this problem is {a2,a4,a1,a3,a7,a5,a6}
penality , w5+w6=50

I tried for a long time and couldnt get this solution

Can anybody help me find a way to solve the problem.

•

Join Date: Jan 2008

Posts: 1

Reputation: Akshay Degwekar is an unknown quantity at this point

Solved Threads: 1

Akshay Degwekar Akshay Degwekar is offline

Offline

Newbie Poster

Re: Greedy Algorithm-task scheduling problem

Jan 25th, 2008

First sort the input by deadlines in ascending order then select the tasks whick incur maximum penalties to do first.

i have pasted the code and the problem. You will have to negate the bonuses.

A teacher assigns homework at the beginning of the first day of class. Each homework problem carries one mark, plus a bonus if submitted within a specified number of days. The deadline for earning the bonus and the number of bonus marks are different for each homework problem. For instance, if a problem has a deadline of 6 days and carries bonus 10 marks, then it earns 10 bonus marks provided it is submitted before the end of the 6th day.
Each homework problem takes exactly one day to complete. For instance, suppose there are seven problems with deadlines and bonuses as follows:
Problem number 1 2 3 4 5 6 7
Deadline for bonus 1 1 3 3 2 2 6
Bonus marks 6 7 2 1 4 5 1
The maximum number of bonus marks one can obtain is 15, which can be achieved by completing the problems in the sequence 2,6,3,1,7,5,4. Note that there are also other sequences that achieve the same effect.
Your task is to find a schedule to complete all homework problems so as to maximize bonus marks.
Input format
The first line contains an integer N, indicating the number of homework problems. This is followed by N lines (lines 2,…,N+1), each containing two integers. The first integer on line i+1 (1 ≤ i ≤ N) is the deadline for the ith homework problem and the second integer on line i+1 is the number of bonus marks assigned to the ith homework problem.
Output format
A single integer indicating the maximum number of bonus marks that can be obtained.
:
You may assume that 1 ≤ N ≤ 1000.
Example:
Here is the sample input and output corresponding to the example discussed above.
Sample Input
7
1 6
1 7
3 2
3 1
2 4
2 5
6 1
Sample Output
15

Help with Code Tags

(Toggle Plain Text)

/*Homework*/
#define Size 1000
#include<stdio.h>
#include<stdlib.h>

struct Homework /*The structure is one homework task*/
{
  int Deadline;
  int Bonus;
};

struct Homework Tasks[Size];


int Compare(const void *_a,const void *_b)
{
  struct Homework *a,*b;
  a=(struct Homework *)_a;
  b=(struct Homework *)_b;
  if(a->Deadline>b->Deadline)return 1;/*If the deadline is less then the number is strictly before*/
  if(a->Deadline<b->Deadline)return -1;
  if(a->Bonus<b->Bonus)return 1;/*When the days are equal the one with a higher bonus is to be given higher priority*/
  if(a->Bonus>b->Bonus)return -1;
  return 1;  
}

void printTasks(int N)
{
int Cnt;
for(Cnt=1;Cnt<=N;Cnt++)
  printf("\n%d %d",Tasks[Cnt].Deadline,Tasks[Cnt].Bonus);
}

int main()
{
  int TotalTasks;
  int TotalBonus=0;
  int Cnt;int Days=1;
  scanf("%d",&TotalTasks);
  
  for(Cnt=1;Cnt<=TotalTasks;Cnt++)
    scanf("%d %d",&Tasks[Cnt].Deadline,&Tasks[Cnt].Bonus);
  
  qsort(&Tasks[1],TotalTasks,sizeof(struct Homework),Compare);  

  for(Cnt=1;Cnt<=TotalTasks;Cnt++)
  {
    if(Tasks[Cnt].Deadline >= Days)/*If the job can be completed then add the bonus to the last bonus*/
      {TotalBonus+=Tasks[Cnt].Bonus;Days++;}/*The day is to be incremented iff a task is done*/
    else /*If the job cannot be completed then the bonus till now is equal to the last bonus*/
      TotalBonus=TotalBonus;
  }
  printf("%d",TotalBonus);
  return 0;
}

•

Join Date: Dec 2008

Posts: 2

Reputation: haider_up32 is an unknown quantity at this point

Solved Threads: 2

haider_up32 haider_up32 is offline

Offline

Newbie Poster

Re: Greedy Algorithm-task scheduling problem

Dec 11th, 2008

Task Scheduling Problem

ai (task) 1 2 3 4 5 6 7
di (deadline) 4 2 4 3 1 4 6
wi (weight) 70 60 50 40 30 20 10

1.Pick a task with the maximum weight :- a1 with penalty 70 and deadline 4 ,so place it in 4th slot.Now slots from 0-1,1-2,2-3 are empty.

X,Y,Z,a1

2.Now we can select between a2(d2)-->p=60 ; a3(d4)-->p=50 ; a4(d3)-->p=40 ; a5(d1)-->p=30;a6(d4)-->p=20.Others have deadline after 4 time slot

Now out these 5 we have to select best 3 according to penalty.We will skip a5,a6 as it has least penalty

==a4,a2,a3,a1

==a2,a4,a3,a1

Both of these combinations save penalty if u check their deadlines.

==a2,a4,a1,a3 is also correct

3. Now all time slots uptil 4 are filled and we are left with

a2,a4,a3,a1,A,B,C .We can save the penalty of t7 by executing with deadline of 6 that is either at position a or b,so it becomes:-

==a2,a4,a3,a1,a5,a7,a6
==a2,a4,a3,a1,a6,a7,a5
==a2,a4,a3,a1,a7,a5,a6

which has min penalty of w5+w6 = 50

Last edited by haider_up32; Dec 11th, 2008 at 3:56 pm. Reason: formatting

•

Join Date: Oct 2009

Posts: 1

Reputation: kdigu is an unknown quantity at this point

Solved Threads: 0

kdigu

Offline

Newbie Poster

Oct 13th, 2009

ai (task) 1 2 3 4 5 6 7
di (deadline) 4 2 4 3 1 4 6
wi (weight) 70 60 50 40 30 20 10

Sort them in decresing order of weight

Greedily select the task with max weight
Its deadline is 4, so put it in slot 4.
1 2 3 4 5 6 7
a1
Now select a2. Deadline is 2, so put it in slot 2.
1 2 3 4 5 6 7
a2 a1

a3, deadline is 4. 4 is occupied, so put it in a slot less than 4, that is unoccupied and has the max value. Here 1 and 3 are unoccupied, so put it in 3. Or move backwards until u find an empty slot. If no slot found put it in the last slot.

1 2 3 4 5 6 7
a2 a3 a1
a4, dealine is 4, so put it in 1. Thats the only unoccpied slot less than 4.

1 2 3 4 5 6 7
a4 a2 a3 a1

a5, no empty slots less than 1...put it in 7.
a6 no empty slots less than 4 put it in 6

Add both the penalty's to penalty variable.

a7 deadline 6, put it in 5.

Finally we have
1 2 3 4 5 6 7
a4 a2 a3 a1 a7 a6 a5

Total Penalty 50.

Cormen book solved it using Metroids. So the above sequence is different from cormen. But this is also right.