Activity Selection with Profits

This is the source code of my previous course project "Activity Scheduling with Profits".

Project has been written in C# with ASP.NET.

Fully functional project demo is available from http://cs.sleekkeys.com




Source code of the main algorithm is put as "SchedulerModels.cs", the other supplementary files such as views, images, scripts, controllers are available from the web site.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace EECS.Models
{
public interface ISchedulerService
{
List GetJobsList(Guid deviceId, DateTime start, DateTime end);
void OrderJobsListByFinishTimes(ref List unorderedJobList);
void AttachNearestFinishingJobs(ref List nearestFinishingJobsNotAddedJobList);
int[] FindLargestProfitsWithScheduling(List orderedNearestFinishingJobsFilledJobList);
void GetJobsFromLargestProfitsList(int[] largestProfitScheduling, ref List orderedNearestFinishingJobsFilledJobList);

void SaveRating(Guid userId, Guid jobId, int rating);

void ApplyGreedyApproach(ref List jobs);
}

public class SchedulerModel
{
}

public class SchedulerService : ISchedulerService
{
DbDataContext db = new DbDataContext();

public List GetJobsList(Guid userId, DateTime start, DateTime end)
{
var jobs = (from j in db.Jobs
join r in db.Ratings.Where(x => x.UserId == userId) on j.Id equals r.JobId into r_j
from r in r_j.DefaultIfEmpty()
select new Job { Id = j.Id, Duration = j.Duration, Desc = j.Desc, Name = j.Name, StartTime = j.StartTime, Rating = r == null ? 0 : r.Rating1 }).ToList();

/*
* tmp array with size jobs.Count
* int noOfElementsInBetween = 0
* for i=0 to jobs.Count
* if(jobs[i].StartTime >= startDate && jobs[i].FinishTime >= endDate)
* tmp[noOfElementsInBetween] = jobs[i]
* noOfElementsInBetween ++
*
* result array with size noOfElementsInBetween
* for i=0 to noOfElementsInBetween
* result[i] = tmp[i]
*/
jobs = jobs.Where(x => x.StartTime >= start && x.FinishTime <= end).ToList(); return jobs; } public void OrderJobsListByFinishTimes(ref List jobs)
{
// takes O(n)
// order jobs by finish times(start+processing)
jobs = jobs.OrderBy(x => x.FinishTime).ToList();
}

public void AttachNearestFinishingJobs(ref List jobs)
{
// takes O(nlgn)
// compute H(i) for each element using binary search
int low, high, mid;
int best;
for (int i = 0; i < jobs.Count; i++) { best = 0; // Nearest finishing job found so far. low = 0; high = i - 1; while (low <= high) { mid = (high + low) / 2; if (jobs[mid].FinishTime > jobs[i].StartTime)
{
high = mid - 1;
}
else if (jobs[mid].FinishTime < jobs[i].StartTime) { best = mid + 1; low = mid + 1; } } jobs[i].NearestFinishingJob = best; } } public int[] FindLargestProfitsWithScheduling(List jobs)
{
// takes O(n)
// create an array A to hold the largest profit that we can get by scheduling activities from 1 to i+1.
int[] A = new int[jobs.Count + 1];
for (int i = 0; i < A.Length; i++) { A[i] = 0; } int max = 0; for (int i = 1; i < A.Length; i++) { max = jobs[i - 1].Rating + A[jobs[i - 1].NearestFinishingJob]; if (max < A[i - 1]) { max = A[i - 1]; } A[i] = max; } return A; } public void GetJobsFromLargestProfitsList(int[] A, ref List jobs)
{
for (int i = 0; i < jobs.Count; i++) jobs[i].IsInBestProfitSchedule = false; int j = jobs.Count; int moveTo = -1; while (j > 0)
{
if (moveTo != -1)
{
if (A[j] != moveTo)
{
j--;
continue;
}
else
{
moveTo = -1;
}
}

if (A[j] != A[j - 1])
{
jobs[j - 1].IsInBestProfitSchedule = true;
moveTo = A[j] - jobs[j - 1].Rating;
}
j--;
}
}

public void SaveRating(Guid userId, Guid jobId, int rating)
{
var prevRating = db.Ratings.Where(x => x.UserId == userId && x.JobId == jobId).SingleOrDefault();
if (prevRating == null)
{
db.Ratings.InsertOnSubmit(new Rating { Id = Guid.NewGuid(), JobId = jobId, UserId = userId, Rating1 = rating });
db.SubmitChanges();
}
else
{
prevRating.Rating1 = rating;
db.SubmitChanges();
}
}

public void ApplyGreedyApproach(ref List jobs)
{
jobs = jobs.OrderByDescending(x => (double)x.Rating / x.Duration).ToList();

// Order jobs according to pi/duration in decreasing order.
var remainingJobs = jobs.OrderByDescending(x => (double)x.Rating / x.Duration).ToList();

while (remainingJobs.Count > 0) // Try to use all the jobs
{
// Get the job which gives best profit proportional to duration and then get the next best job which is available after first job.
var selected = remainingJobs[0];

jobs.Where(x => x.Id == selected.Id).Single().IsInBestProfitSchedule = true;

// Remove jobs whose start time or finish time is in between of chosen jobs start and finish time.
remainingJobs = remainingJobs.Where(x => (x.FinishTime <= selected.StartTime && x.StartTime <= selected.StartTime) || (x.FinishTime >= selected.FinishTime && x.StartTime >= selected.FinishTime)).ToList();
}
}
}
}