Dear Soroush

Could you be more specific?

What are you scheduling for?

I have worked a lot on scheduling but I am not sure I understand your needs

Dear Nolberto

Thank you for your answer and your consideration,Suppose that we have an activity on node graph that represent a Computer program or An Algorithm

each node represents A task with given time to get processed and each edge shows the communication between tasks(precedence constraint)they also shows the communication cost.now suppose that we have some cores(or computation resources)that we want to deploy to process the whole graph,I want to find a answer to these question:

1.which task(or tasks) should be processed on which core(cores),how to assign them to resources.

2.In what sequence should them be processed on cores

In order to minimize the completion time(SO called Makespan)

I am aware of that the problem is NP hard and should be tackled by Heuristics.

I would be very thankful to get some help on aforementioned problem,any idea of an expert or even any thesis or stuff that could be helpful.thank you

P.S:I have already read some books on scheduling like cheduling - Theory, Algorithms, and Systems,Mael L. Pinedo and task scheduling for parallel systems, Oliver Sinnen

I am also working on Job Scheduling on Cloud and other distributed systems. As Mr Nolberto said, your objective will make your scope clear. For me I focus on Cost and Performance trade-off. I also use Application models which can be represented as Directed Acyclic Graphs. So, your System Model, the Application Model and the Objective function ( Minimize Makespan, optimize execution flow, Reduce communication cost, . . . ) can result in different strategies. By the weekend I will try to send you materials I have in hand. Good luck

Gang scheduling

Dear Moise

Thank you for your aswer,I really appreciate your help.

I have a general question too:

To my knowledge most of optimizations have been done by using Genetic Algorithms,and the number of papers and books in this area is huge, my question is: Is there really any chance to find a better solution to these kind of problems using GA algorithms?

I would be very pleased to hear from you

Good luck

Dear Esmail,

Thank you for your answer,I have read a little bit about gang scheduling,it seems gang scheduling is old days method and not suitable for this case Am I wrong?,can you explain it a little more?

thank you

Regards

Hello,

As your advisor said, you need to specify the problem more clearly. For example, how did you model tasks (periodic or aperiodic or sporadic)? Are tasks independence or not? How to define the priorities of tasks? Is Preemption allowed or not? ....

For any scheduling algorithm, we need to formulate the problem and specify assumptions. If we have no such information, the algorithm might be: store the requests in a queue and process one as long as a core is free to be used.

By the way, I recommend you two related papers:

[1]. B. B. Brandenburg, "On the Scalability of Real-Time Scheduling Algorithms on Multicore Platforms: A Case Study"

[2]. S. Boyd-Wickizer et al, "Reinventing Scheduling for Multicore Systems"

Hopefully, you can solve your problem.

Since you're naming GA, this sounds like a classic static (offline) task-graph scheduling combined with task assignment. There is a large amount of work done in the area, from GA (if one has no much insight into the problem) to ILP, Constraint Programming and all sorts of heuristics. You might want to look at list-scheduling as a start.

Dear Troung,

Thank you for your Answer and Your Time,I didn't have any Idea About Periodic,Aperiodic and Specially Sporadic Concept in Scheduling,thank for mentioning them,Tasks are Dependent,represented by Arcs(Edge)of DAG,I am not Quite sure about Preemption,cause I think in a DAG model of computer program tasks Are Decomposed till the level of smallest task which are represented by Nodes in DAGs and can't be decomposed any more,So I personally think preemption should not be allowed.

Thanks for the recommended Papers,

Regards,

Soroush

Dear Flavius,

Thank you so much for your Answer, yes my Problem is categorized in offline scheduling,I have read A lot about List scheduling and Clustring.

ILP or Constraint programming are very good but as you know those methods might not be useful considering time and space complexity of them and heuristics are much Attractive to that extend.

Again I have to ask everybody who kindfully answered me,Is there any hope to find An Algorithm(GA,SA..)or method so it can Reduce Makespan?

Regards,

Soroush 

Hey soroush,

Have you looked at Minimax method to find a job-core assignment?  

This method can easily answer to your first question (your answer to Nolberto Munier ).

I hope this method helps you

Thank you Shahriar,I will search the keyword you recommended.

Regards,

Soroush