I cannot find a way to model the following problem, maybe one of you guys can help me:
Consider the following machine scheduling problem: n jobs, denoted by 1,...,n, need to be scheduled on a single machine. The machine can process at most one job at a time and it is not allowed to preempt a job, i.e., as soon as a job has been started, the machine must process this job until completion. The processing time, that is, the time it takes to fully process a job, is Pj (j=1,...,n).
The goal is to minimize the sum of completion time,i.e., let Cj denote the completion time of job j (in a given schedule).
The fact that the machine can only process one job at a time and is not allowed to preempt jobs, implies that either job j has to start after job k has finished or the other way around.
Formulate the above problem as an integer (linear) program, using the decision variables Cj. (You might need some additional variables.)
Please, help me... |
