# Job Shop Problem

Not what you're looking for?

Suppose you have N jobs that have to be processed on a single machine. For

i = 1, 2, . . . ,N, job i requires pi units of time on the machine, and has weight wi. The objective is to schedule these jobs so as to minimize the sum of the weighted completion time of all the jobs, where the completion time of job i is the time at which job i finishes. Note that at most one job can run on the machine at any time. For example, let N = 3, p1= 1, p2 = 2, p3 = 3, and the weights are w1 = 2, w2 = 1, w3 = 0. If the jobs are scheduled in the order 231, then the completion time of job 2 is 2, completion time of job 3 is 5, and the completion time of job 1 = 6. The value of the objective function for this schedule is 2 à? 6 + 1 à? 2, which is 14. (We consider schedules that are non-preemptive: any job started on the machine cannot be interrupted. In other words, if we decide to schedule job 2 as the first job, we have to let it run until time 2, which is when job 2 finishes.

Define T = ∑...

Clearly, it is enough to consider schedules in which all of the jobs are completed by time T. (In other words, there is no benefit to keeping the machine idle when there are jobs to be processed.) For i = 1, 2, . . . ,N, and t = 1, 2, . . . , T, let your decision variables be Xit, which is 1 if job i completes at time t, and 0 otherwise. Formulate the given scheduling problem as a linear (integer) programming problem involving these decision variables. (Hint: You need to incorporate the non-preemptive condition and the condition that at most one job can run on the machine at any time.)

Please see attached for equation.

##### Purchase this Solution

##### Solution Summary

This solution is comprised of a detailed explanation to answer job shop problem.

##### Purchase this Solution

##### Free BrainMass Quizzes

##### Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

##### Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

##### Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

##### Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

##### Probability Quiz

Some questions on probability