Consider the following machine scheduling problem: A set {J1, ,Jn} of jobs needs to be scheduled onto m parallel machines M1 , Mn. Unless specified otherwise, all machines are continuously available from time 0. The time requirements for processing these jobs are, respectively, p1, pn > 0. Each of these n jobs needs to be processed without interruption on one of the m machines. We assume that any machine can process at most one job at a time and there is no machine idle time until the machine has processed all the jobs assigned to it.

Suppose there is only one machine (i.e.,m = 1). The objective is to determine the processing sequence of all the jobs in such a way that the sum of individual job completion times is minimized. For example, suppose n=2, P1 = 2 and P2 = 1. Then under processing sequence of (J1, J2), the completion times of these two jobs are 2 and 3, respectively. Formulate the problem as a binary integer program (BIP). (Hint: Introduce binary variable Xij, which is 1 if and only if job Jj is sequenced in position i for all i,j = (1, , n)