2
$\begingroup$

I would like to seek some modeling advice on the following:

Say for instance I have 5 nodes representing workstations of the operation of 5 jobs, and that I have less than 5 vehicles. Say I have two vehicles.

It is obvious that only 2 workstations will be serviced at the beginning while the rest will have to wait till either of the 2 have finished processing.

Hence, say for instance, vehicles have been assigned to visit stations 1 and 2, with the start time of each station being the distance traveled, and that both vehicles depart from the depot at time 0.

The difficulty resides in finding the minimum of the 2 completion times, so that the earliest of the remaining 3 stations to be served is approximated by setting it to be greater than or equal to that of the minimal completion times of both said stations.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Assuming that the routing of the vehicles is part of the solution, you will likely need a ton of binary variables. The binary variables will determine both which vehicles serve which stations and also the sequencing. There are multiple ways to approach this. For instance, you might have $x_{ij}=1$ if vehicle $i$ serves station $j$ and $y_{jk}=1$ if station $k$ is served immediately after station $j$ by the same vehicle that served $j$, or you might have $x_{ijk}=1$ if vehicle $i$ serves station $k$ immediately after serving station $j$.

Once you have the binary variables pinned down, you can use continuous variables to capture the start times and end times for operations. This typically involves "big M" constraints. For example, using the triple-subscripted $x$ above, suppose $s_j$ and $e_j$ are continuous variables capturing the start and end of operations at station $j$ and $p_{ij}$ is a parameter representing the processing time at station $j$ if served by vehicle $i$. (You can drop the $i$ subscript if processing time is independent of the vehicle doing the processing.) Getting the end time from the start time is easy:$$e_k = s_k + \sum_i p_{ik} \sum_j x_{ijk}.$$(I'm assuming here that each vehicle visits each station at most once.) Getting the start time from the end time of the previous station is a bit trickier. Assume that $t_{ijk}$ is a parameter representing the transit time for vehicle $i$ from station $j$ to station $k$. (Again, drop the $i$ if all vehicles operate at the same speed.) The start time constraints look like$$s_k \ge e_j + t_{ijk} -M(1-x_{ijk})\quad \forall i,j.$$ If $x_{ijk}=0$, the constraint is vacuous. if $x_{ijk}=1$ (vehicle $i$ goes to station $k$ immediately after station $j$), station $k$ starts no earlier than the ending time at station $j$ plus the transit time between stations.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Dear Prof Rubin, thank you for your inputs. I guess it is difficult to describe the problem on paper. I am trying to strengthen a flexible jobshop problem for benders decomposition by considering the distances between stations while. Ot explicity considering the vehicles. I am trying to include the distance for the initial operations of each job without explicitly considering the distances between the distances between the stations that are selected for processing the initial operations of each job. $\endgroup$
    – Mike
    May 12, 2021 at 4:28
  • $\begingroup$ Also the distances between each station that are used to process the second to last operation of each job will also be considered using the inequality constraints suggested by you.Kindly correct me if I am wrong, the restricted master problem should not be too difficult nor easy to solve as it is a compromise between having too many iterations as too much slack is present in the master problem resulting in the permutations of solutions such as jobshop machine assignment while retaining the same lower bound. $\endgroup$
    – Mike
    May 12, 2021 at 4:38
  • $\begingroup$ As this is a discrete problem, I suppose the best bet is to strengthen the master problem so as up the bounds as much as possible after each iteration as to effectively use the optimality cut, to weed out the said solution permutations. This is the rationale for approximating the problem for the initial operation timings of the remaining jobs, or else there will be negligible difference from solving the original problem. $\endgroup$
    – Mike
    May 12, 2021 at 4:40
  • $\begingroup$ I'm not sure I follow you (actually, I'm sure I don't), but if you have jobs with fixed sequences of tasks but choices of which stations perform the tasks and you want to bound start times, you can say that the start time of a successor task is at least the end time of the predecessor plus the shortest transit time between any pair of stations capable of performing the respective tasks. $\endgroup$
    – prubin ♦
    May 12, 2021 at 15:40
  • $\begingroup$ As far as Benders goes, a "weak" master problem will result in more constraints being unearthed in the subproblem(s). On the other hand, efforts to strengthen the initial master problem might result in a bunch of master constraints that are unnecessary (implied by stronger constraints the subproblem(s) will find). Those redundant master constraints will nonetheless burden the solver a bit. So it's guesswork how much benefit you will find in trying to tighten the master. $\endgroup$
    – prubin ♦
    May 12, 2021 at 15:43

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.