0
$\begingroup$

I have gone through a list of scheduling algorithms and their implementation, however couldn't find any reference to implement an algorithm that solves the following problem.

Given an array of processes having n process, the i'th process being represented by:

Arrival[i] representing its arrival time,

Depart[i] representing the time when a process will be terminated (processed or unprocessed doesn't matter) and

Time[i] representing the time required to serve the process, and

Preferred[i] representing a Boolean value (true if that process is preferred, false otherwise)

We need to schedule the processes to maximize processing of preferred processes. A preferred process will have Preferred[i] as true.

The constraint being only a single process can be served at a time, and if a process departs before its completion its said to be unprocessed.

In case of a tie following rules apply:

  1. Serve maximum number of processes (preferred and non- preferred combined).
  2. Minimize the Processing time.

Any leads would be appreciated.

$\endgroup$
  • $\begingroup$ What does "maximize processing of preferred processes" mean? Can you give a clearly defined objective function that you are trying to maximize? How do you measure/quantify "processing of preferred processes"? Are you maximizing the number of processes that complete? What is a "preferred" process? I don't see any explanation of what preferred means or how we tell what is a preferred process. $\endgroup$ – D.W. Mar 14 '18 at 18:41
  • $\begingroup$ What approaches have you tried? Where did you get stuck? Have you tried applying dynamic programming? Have you tried greedy algorithms? Have you tried working through some small examples by hand to see if you can spot any patterns? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – D.W. Mar 14 '18 at 18:41
  • $\begingroup$ An example of what D.W. is getting at is: Suppose there are 3 processes, a preferred one that takes 2 time units and two non-preferred ones that each take 1 time unit. They all arrive at time 0 and depart at time 2. Is it better to take the single preferred process, or both non-preferred? Note: Just giving the answer to this specific example is not enough -- you need to describe a preference rule that answers every possible such case. $\endgroup$ – j_random_hacker Mar 14 '18 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.