Suppose there are n jobs and m machines and each job must be processed on each...

Transcribed Image Text:

Suppose there are n jobs and m machines and each job must be processed on each machine. For each job, the machine order is fixed, that is, job j must first be processed on machine j(1) and then on machine j(2), and so on. A machine can only process one job at a time, and once a job is started on any machine it must be processed to completion. The objective is to minimize the sum of the completion times of all of the jobs. The data that specify an instance of the problem are m, n, and pij for j = 1,...,n and i = 1,...,m, which is the processing time of job j on machine i, and the machine order j(1),...,j(m), for each job. Formulate the problem and solve the following instance: (Pij) i=1,...,4; m = 4 n = 8 1,...,4;j=1,...,8 = job 123456 7 8 3 10 5 6 6 4 10 3 12 11 2 9 1 1 4 4 9 4 3 3 7 6 3 1 7 6 8 Order 2 2 2 3 1 1 8003 4 1 4 3 4 3 2 2 3 2 4 1 4 2 2 1 4 9 6 12 11 4 5 3 1 4 6 Table 1: Processing order of each job 3 2 Suppose there are n jobs and m machines and each job must be processed on each machine. For each job, the machine order is fixed, that is, job j must first be processed on machine j(1) and then on machine j(2), and so on. A machine can only process one job at a time, and once a job is started on any machine it must be processed to completion. The objective is to minimize the sum of the completion times of all of the jobs. The data that specify an instance of the problem are m, n, and pij for j = 1,...,n and i = 1,...,m, which is the processing time of job j on machine i, and the machine order j(1),...,j(m), for each job. Formulate the problem and solve the following instance: (Pij) i=1,...,4; m = 4 n = 8 1,...,4;j=1,...,8 = job 123456 7 8 3 10 5 6 6 4 10 3 12 11 2 9 1 1 4 4 9 4 3 3 7 6 3 1 7 6 8 Order 2 2 2 3 1 1 8003 4 1 4 3 4 3 2 2 3 2 4 1 4 2 2 1 4 9 6 12 11 4 5 3 1 4 6 Table 1: Processing order of each job 3 2

Answer rating: 100% (QA)

The problem you described is known as the Permutation Flowshop Scheduling Problem It is a wellknown scheduling problem in operations research and invo... View the full answer