0
$\begingroup$

I am trying to model a job-shop scenario where - given a certain number of workers (W) and parts (P) such that P>W - each worker spends each shift (k) working on a specific part. Due to reasons of maintaining efficient workflows, it is preferred that a worker keeps working on that same part for the entire week (i.e. all 5 shifts in a week). At the outset, it doesn't matter which part they start on, but once they are scheduled for a part it is preferred they stick to it. I have thought to model it in the following way.

My question is: does this makes sense or if there are any negative consequences to this method of modelling? One thing I do not like is there ends up being many $\delta_{w,p}$ constraints.

$Z_{w,p,k} \in \lbrace 0,1 \rbrace$ = Worker W making part P on shift K

$\delta_{w,p} \in \lbrace 0,1 \rbrace \ge Z_{w,p,k}$ for each k (to check if a worker is working on that part that modelling period or not)

$\delta_{w} = \sum \delta_{w,p} $

And then either minimizing the sum of all $\delta_{w}$ or constraining their maximum.

$\endgroup$
4
  • $\begingroup$ Do you require that every part be worked on in every period? Can multiple workers work on the same part at the same time, and if so is it efficient (meaning two workers on a part for one period is equivalent to one worker on the part for two periods)? $\endgroup$
    – prubin
    Mar 27 at 15:29
  • $\begingroup$ Hi Professor. The answers are: no and no. This is because we have specific tools and dies needed for each part. So in general, a worker may work on more than one part per modelling period, but it is preferable (but not required) that any part is only made by one worker per modelling period. Thank you for the clarification. $\endgroup$ Mar 27 at 15:38
  • $\begingroup$ Is minimizing the number of workers active in a period a criterion, or do you just want to minimize the number of workers assigned to the same part and do not care how many workers are used? $\endgroup$
    – prubin
    Mar 27 at 19:21
  • $\begingroup$ Just minimize number of workers assigned to the same part. Separately we try to maintain a certain range in the number of workers per shift (having 10/10/10 is typically better than 5/15/5, even if total number of workers is larger - just from a worker management point of view). We have that handled separately in the model but if it makes more sense to handle them together then whatever works best. $\endgroup$ Mar 27 at 20:48

3 Answers 3

1
$\begingroup$

Your approach seems appropriate to me, although I would change the $\delta_w$ variables to $\delta_p = \sum_w \delta_{w,p}$ and then minimize the largest value by minimizing a new variable $z$ subject to $z\ge \delta_p$ for all $p.$

$\endgroup$
1
$\begingroup$

More than it has been a job shop problem, it sounds like an assembly/fabrication sequencing problem. You can formulate this as of a variant of the bin packing problem with additional constraints to capture what you want. The objective is to minimize the number of workers that are being assigned to perform parts. Also, you can already define a specific order of jobs in which can be performed simultaneously by a specific worker to balance the workload of each worker. As an attempt, I tried with the following assumption and the results would be:

parts= {(part1-1, part1-2, part1-3), (part2-1, part2-2, part2-3), (part3-1, part3-2, part3-3)};
workers = {worker1, ..., worker9};
processing time= {
part1-1 03
part1-2 02
part1-3 02
part2-1 05
part2-2 01
part2-3 02
part3-1 02
part3-2 2.5
part3-3 3.5
};
shift = {8}; # a normal 8hrs shift

Result with determining an order of parts to perform simultaneously:

            worker1     worker2     worker3

part1-1                   1.000
part1-2                   1.000
part1-3                   1.000
part2-1                               1.000
part2-2                               1.000
part2-3                               1.000
part3-1       1.000
part3-2       1.000
part3-3       1.000

Result with an arbitrary performing order of jobs:

            worker1     worker2     worker3

part1-1                               1.000
part1-2       1.000
part1-3       1.000
part2-1                               1.000
part2-2       1.000
part2-3       1.000
part3-1                   1.000
part3-2                   1.000
part3-3                   1.000


 
$\endgroup$
0
$\begingroup$

I'd model it as
$ K_p z_{w,p}^k - \sum_{t=1}^{k-1} z_{w,p}^t \le \sum_{t=k+1}^{K_p} z_{w,p}^t \ \quad \forall w,p \quad \forall k$
where $ K_p$ is total number of shifts generally required to complete part $p$, should be a parameter.

Edit: Your constraint $z_{w,p}^k \le \delta_{w,p}$ is equivalent to $ \sum_k z_{w,p}^k$

So you either minimize
$\sum_w \sum_p \sum_k z_{w,p}^k$

Or

$ \sum_w \sum_k z_{w,p}^k \le \delta_p$

Then $min \sum_p \delta_p$

$\endgroup$
1
  • $\begingroup$ To be clear, it does not take multiple shifts to complete a part p - instead numerous parts can be made each shift. $\endgroup$ Mar 27 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.