3
$\begingroup$

The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take anything from 5 mins to 10 mins. The list of jobs and their duration interval is given to the scheduler and the aim is to minimize the time all jobs would be finished. In interval scheduling, the job start and end time is given and the length is fixed. Here, the job can start and end anytime (should be done in whole though) but its duration (length) is not exactly known.

I searched the literature for this problem but couldn't find it. Is there any keywords I can use or any reference for this problem? Is it well-defined?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I searched for "job shop scheduling uncertain processing times" and came up with this: http://www.waset.org/journals/waset/v64/v64-190.pdf. I hope it helps.

I think you will find that the best approximation algorithm is going to depend on the probability distribution of completion times. An algorithm for exponentially distributed times might be very different than an algorithm for a uniform distribution.

I think you will also need to trade off expected completion time vs. variance. With known completion times a decent approximation algorithm is Coffman's list scheduling algorithm: sort the jobs by length (longest to shortest) and then schedule greedily (next job starts as soon as a machine is free.) With uniform completion times you might try sorting by best-case completion times, expected completion times or worst-case completion times, and you would be getting different answers.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the answer. The paper you sent above is not exactly what I am looking for. In that paper, each job has a set of operations, each should be completed before the next operation. $\endgroup$
    – Mohsen
    Jul 4, 2013 at 3:53
  • $\begingroup$ Yes, job shop scheduling is a generalization of what you are asking for. You are doing job shop scheduling where each job has a single operation. $\endgroup$
    – Wandering Logic
    Jul 5, 2013 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.