Capacity constraints in job shop scheduling

  • 3 January 2023
  • 6 replies
  • 198 views

Badge +4

Hi all, 

I am creating a job shop scheduling model in AIMMS for my MSc thesis. The model plans jobs j of production orders i backwards from their due date. The main (nonnegative) decision variables are: 

  • StartTime(i,j) = the start time of production order i job j 
  • EndTime(i,j) = the end time of production order i job j 

The only thing I still need to add is that capacity may not be exceeded. I have the following information: 

  • Capacity(j) = total capacity of job j in one time bucket 

Now I need some counter / variable looking like:

  • x(i,j,t) = the amount processed of operation i, job j in time bucket t. Where time bucket 1 = [0,1], time bucket 2 = [1,2] et cetera. 

See the figure below for my current data, I want to retrieve the following x(i,j,t) values: 

  • x(1,COAT,1) = 0.5 (from 0 to 0.5)
  • x(1,PRO,1) = 0.5 (from 0.5 to 1)
  • x(1,PRO,2) = 0.7 (from 1 to 1.7)
  • x(1,PW,2) = 0.3 (from 1.7 to 2) 
  • x(1,PW,3) = 0.5 (from 2 to 2.5)

 

Does someone have an idea on constraints to retrieve the values for x(i,j,t) as shown in the example?


6 replies

Userlevel 2
Badge +3

Hi MZwanenburg,

I am currently having difficulty understanding all aspects of your optimization problem. To clarify, could you please provide more information on the following:

  • What do you mean by "production order"? Is it referring to a customer order or is it related to the production sequence?
  • Could you explain what you mean by the "capacity of the job"?
Badge +4

Hi @Zsolt Mihály , 

  • I have production order i that should follow the job route with j jobs. So Production order i need to follow a route {j1, j2, j3, j4}. In my example: production order 1 need to follow the steps COAT → PRO → PW. 
  • The jobs have capacity, e.g. for job COAT there can at most be processed two COAT jobs simultatenously. So for example:
    • If production order 1 job COAT starts at x=1 and needs 2 units to process (so ends at x=3) and; 
    • Production order 3 job COAT also starts at x=1 and needs 3 units to process (so ends at x=4)  then; 
    • Production order 5 job COAT cannot start early than x=3 since then a spot is available again 

My solution of start and ends times is given by StartTime and EndTime. The parameters StartBucket and EndBucket is just the StartTime and EndTime rouneded up to an integer. 

Userlevel 2
Badge +3

I think that I understand your question better now . My terminology is a little bit different from yours. If that’s also intresting, then I can explain it to you.

 

Back to your question:

The constraint you need: sum[i, x(i,j,t] <= Capacity(j) for each (j,t)

You have to fulfill the constraint for each job and for each time bucket. So you have a constraint domain index (j,t). The constraint says that the total production should be lower than the capacity.

 

What do you think about it?

 

 

 

Badge +4

Hi @Zsolt Mihály , 

Yes that capacity constraint I understand. But how do I receive x(i,j,t)? 

Since I only have a starting time StartTime(i,j). 

 

Userlevel 2
Badge +3

If you have a set of time buckets. Then you need neither start nor end time, since they are parameters of time buckets.

On the contrary, if you have start and end times,  you don’t need time buckets. In that case you need to write different kind of constraints to make sure that the maximum capacity won’t be exceeded.

If you have a time bucket set, then you can handle discrete times. If you have start and end times, then you can handle continuous time. I suggest not to mix the two ways of time handling.

So which is your case?

 

 

 

Badge +4

Hi @Zsolt Mihály ,

A bit late but this is again relevant for my problem. 

It is the second case, I do not want to use time buckets. 

  • I have an integer decision varaiable x(p,j) that provides the week in which a job is planned; 
  • I have a processing time parameter for each job in a production order p(p,j);
  • I have a capacity parameter for a job per week cap(j);  
  • I need a constraint that ensure that the capacity per week is not exceeded. 

I thought about a constraint in the following way: 

sum[p | val(t) = x(p,j) , p(p,j)], however, then I am mixing the two cases. Which is not suggested (besides it is not allowed to use a decision variable in a summation in a constraint in AIMMS). 

But still I think that I need a summation that sums the processing times handled in a specific week. What do you think? 

Reply


Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator