0

scheduling n jobs on m machines, each job has a different processing time on each machine. all schedule has n positions indexed by l as l =0,1,...,n as position 0 for dummy job

Used this mathematical model to present the problem

min Cmax
subject to:

$$ Cmax \ge C_j $$ $$ C_j = \sum_{i=1}^n \sum_{l=1}^n x_{ijl} P_{ij} \forall j=1,2,\cdots m$$

$$ \sum_{j=1}^m \sum_ {l=1}^n X_{ijl} =1 \forall i =1,\cdots n$$

$$ \sum_{i=1}^n X_{ijl} \le 1 \forall j =1,\cdots m \forall l =1,\cdots n$$ $$X_{ijl} \in {0,1} $$

the problem is I have coded in Lingo but it schedules jobs in same position but on different machines, for example $ X_{1,2,3} =X_{3,1,3} =1 $ so I added this constraint: $$ \sum_{j=1}^m \sum_{i=1}^n X_{ijl} = 1 \forall l=1,\cdots n$$ but it schedules all jobs in only one machine. what is the problem

Enas Esh
  • 15
  • You might want to explain your notations, or at least what textbook's conventions you are following. Also, you might be mixing-up/reusing some variables... like, how can $C_j$ be dependent upon $j$ if $j$ is just a summation index that disappears after being summed over? – DotCounter Nov 04 '21 at 18:34
  • Cmax is maximum completion time of all jobs. Cj is the completion time on machine j – Enas Esh Nov 04 '21 at 20:15
  • Cmax is the maximum completion time of all jobs. Cj is the completion time on machine j. Xijl is a binary variable that equals 1 if job i is scheduled on machine j. Pij is the processing time of job i on machine j. the problem objective function is the minimization of Cmax. the first constraint computes the completion time on machine j. constraint 2 ensures that each job is scheduled on one machine at only one job. constraint 3 ensures that no more than one job can be processed at any position on a machine. – Enas Esh Nov 04 '21 at 20:24
  • and what is the indexing issues, plz? – Enas Esh Nov 05 '21 at 11:44
  • sorry, it is a typo mistake. but it – Enas Esh Nov 05 '21 at 13:41
  • $$ C_j = \sum_{i=1}^n \sum_{l=1}^n X{i,j,l} * P{ij} \forall j=1,2, \cdots , m $$ – Enas Esh Nov 05 '21 at 13:44
  • I checked the code and it was correct – Enas Esh Nov 05 '21 at 13:47
  • I have just edited it. – Enas Esh Nov 05 '21 at 14:36

1 Answers1

1

After your changes, the formulation now looks correct. There is nothing to prevent all jobs from being assigned to one machine, and doing so will be optimal if that machine is sufficiently faster than all others. If you suspect that a better solution uses more than one machine, you can try fixing all $x_{i,j,l}$ variables to that solution and call the solver to see whether it accepts this solution as feasible and yields the objective value you expect.

RobPratt
  • 45,619
  • is not minimization makespan(maximum completion time of all machines) preventing scheduling all jobs on just one machine? – Enas Esh Nov 06 '21 at 12:17
  • Not if all the other machines are slow. – RobPratt Nov 06 '21 at 12:26
  • these jobs are independent of each other, and the processing time is uniformly distributed. when I coded the last constraint in a different way it works. and now, all positions are occupied by jobs. – Enas Esh Nov 06 '21 at 15:39