1
$\begingroup$

I am reading about https://en.wikipedia.org/wiki/Job-shop_scheduling and https://en.wikipedia.org/wiki/Optimal_job_scheduling. Such scheduling is possible if we know the number (amount) of operations (intensity of operations). But what about the following situation: operation A receives A1, A2 amount of materials 1 and 2 and outputs AO3, AO4 amount of materials 3 and 4. Operation B recieves B1, B3 amount of materials 1 and 3 and outputs BO5 amount of material 5.

How we can incorporate in the job-shop scheduling problem the constraint, that the intensity of operation B depends on the availability of material 3 and hence the intensity of operation B is determined by the intensity of operation A which itself is dependent on the availability of materials 1, 2, the availability of respective machine and staff for operation A. And, of course, the inventory of materil 3 can also be available but with the respective costs.

What is the name (term, keyword) for general job-shop scheduling problem that incorporates the flow of materials as well?

$\endgroup$
4
  • 1
    $\begingroup$ I don't understand what you mean by "intensity of operations" and by "operation X receives Y amount of materials". Does that mean that operation X requires some amount Y of a renewable or non-renewable resource? $\endgroup$
    – fontanf
    Oct 6 at 11:54
  • $\begingroup$ Operation required 5.5 units of good 1 and 6.5 units of good 2 and it produces 2.2 units of good 3. Operation can not proceed if there is not enough goods 1 or 2 available. Such constraint means that we can not plan the high intensity of downstream operations if the upstream operations had not been in enough intensity. $\endgroup$
    – TomR
    Oct 6 at 12:05
  • 1
    $\begingroup$ TomR do you mean capacity instead of intensity? $\endgroup$ Oct 6 at 12:07
  • 1
    $\begingroup$ @TomR I don't understand the second sentence. Based on the first one, are you looking for this kind of problem doi.org/10.1007/s10696-012-9152-5 ? $\endgroup$
    – fontanf
    Oct 6 at 12:13
5
$\begingroup$

The general approach, whether you are using a mixed integer linear programming model or a constraint programming model, would be to have (nonnegative) variables representing the inventory of different materials at different times, plus flow constraints saying that the inventory at the end of each period is the starting inventory plus any production of the material minus any consumption of the material.

$\endgroup$
4
$\begingroup$

What you are looking for sounds like, combining the job-shop scheduling problem with material requirement planning or Multi-Periods Job-Shop Scheduling Problem. I am not aware how you would like to use that in the paper or real situation, but in the second one, applying mixed-integer programming (without boosting from the special algorithm like column generation) would be challenging work. Some useful references are:

$\endgroup$
3
  • $\begingroup$ I am programmer coming from sales and the availability of inventory is important aspects in sales. Isnt the same for scheduling? It can be important to minimize the raw and intermediate materials in inventory and ir can be important to produce intermediate goods only in amount needed for immediate further processing. Or I am confusing something here and scheduling usually is about the efficient utilization of machines and workforce and not about minimization of inventory of raw materials. Maybe I am just searching for something that is not important in practice? $\endgroup$
    – TomR
    Oct 6 at 15:58
  • 2
    $\begingroup$ @TomR you'll find problems related to inventory optimization under the keyword "lot sizing" $\endgroup$
    – fontanf
    Oct 6 at 16:08
  • 1
    $\begingroup$ @TomR, in the real situation heuristic approaches like MRP (material requirement planning) is a very powerful tool to encounter with the inventory problem, but if you are willing to use an exact method such as MILP without applying detailed schedule, as fontanf mentioned, the varients of lot-sizing problem is what you are looking for. 👍 $\endgroup$
    – A.Omidi
    Oct 6 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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