Greedy Algorithm-task scheduling problem

[lulusweety]

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.

[Akshay Degwekar]

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

/*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;
}

[haider_up32]

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

[kdigu]

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.

[susano]

i need explanation and implementation for Squeaky wheel optimization (SWO) please,...

[dharmenpunjani]

Hiiii !!!!!!!!
In this problem we have to sort the given Jobs with respect to their penalty in decreasing order .
After that draw time line up to the max deadline.
eg. in this example up to the time unit 6

0 1 2 3 4 5 6

Now from the sorted list of Job select the first one because by taking the job with highest penalty is required for optimal solution.

Now check the time slots from
di - j
to
di - di

where di is the dead line of the Job #i
the value for j = 1 to di

in the first selection of the candidate u will find all the time slot free so keep the job in the last time slot of its dead-line (di-1).

so here our job a1 is scheduled in time slot 3-4.

than in next select the next candidate from the sorted list .

here job a2 then chek the free time slot.

it's dead line is 2 so first check the di - 1 time slot

here it is 2 - 1 = 1

so time slot 1-2 is empty schedule this job a2 in this time slot 1-2.

Next step select the candidate from the sorted candidate and then check for the free time slot for that job

here it is job a3 with d3 = 4

now check di - j
j= 1 to di until u find free time slot.

here 4 - 1 = 3
we have scheduled the job a1 in this time slot so
again 4 - 2 = 2
we have this time slot free so schedule this job a3 in time slot 2-3.

next again select the candidate from the sorted list
here we have job a4 with deadline d4=3

check for the free time slot

3 - 1 = 2
but we have scheduled the job a3 in time slot 2-3 so check for the another time slot

3 - 2 = 1.
but this time slot have the job a2 scheduled so check for the another time slot

3 - 3 = 0
so time slot 0-1 is free and we can schedule job a4 in this time slot 0-1

now again follow the same steps

so we can't schedule the job a5 and a6 because their dead lines are 1 and 4 respectively and we don't have any time slot free up to time unit 4

next we can schedule the job a7 with dead line 6 in slot 6 - 1 = 5
5-6

so we can schedule the jobs
ai(Job/Task) time-slot(before dead line) profit(avoiding penalty)
1 3-4 70
2 1-2 60
3 2-3 50
4 0-1 40
7 5-6/4-5 10
so we have the benefit = 230 or least penalty = 50.

I don't know whether this method is Squeaky wheel optimization (SWO) or not but by using this method u will always get optimal solution.