0
$\begingroup$

I have a production planning / scheduling problem, which I believe is a kind of job shop scheduling problem. But I would like to get some input on what kind of job shop scheduling problem it is and how it can be solved.

I have materials which needs to be produced in a given week, each with a given quantity. These would be the jobs. So I want to create a production plan for the entire week.

To produce each material, I need a specific tool. All materials needs a specific tool. For some of the tools I have multiple of the same kind and for others I only have one. So I might have 100 different materials, but only have 20 tools. So a lot of materials needs the same tool and for some there a multiple and for others there are only one.

In order to produce a material I need the tool associated with the material to be placed into a machine. Each tools can only be placed into a subset of the machines. So e.g. tool A can be placed into machine 1, 2 and 3, while tool B can only be placed into machine 3, 4 and 5. I have more tools than machines.

So #materials > #tools > #machines.

Each material and its given quantity have a production time associated with it.

If I want to change the tools which are placed in a machine, there is a changeover time. However, if I after producing a material on a machine continue to produce another material which requi res the same tool then there is no changeover time. The changeover is dependent on what tool you are changing from and which tool you are changing to. Further, the changeover time from A -> B is not the same as the changeover time from B -> A.

Furthermore, after producing a given quantity on a machine, it needs to be cleaned which requires some cleaning time.

In this problem I want to minimize the make-span and of course come up with a feasible plan.

Want kind of job shop scheduling problem is this, and what would be the best way to solve it?

Improve this question
$\endgroup$
8
  • $\begingroup$ For adding to the answer of the lorax, would you say please, is there any specific route for each material? or after finishing the process on the part in each machine it would be as end item? Also, to enforce the tools-machine constraint, you should define either a specific set/parameter or binary variables to do that. $\endgroup$
    – A.Omidi
    Commented Oct 23, 2020 at 20:32
  • 1
    $\begingroup$ That's right. With regards to you mentioned, the below answer can solve your problem. Many thanks. :) $\endgroup$
    – A.Omidi
    Commented Oct 26, 2020 at 11:45
  • 1
    $\begingroup$ @A.Omidi Do you have a link to some good resources about this problem? Possibly also some examples coded in python? $\endgroup$
    – Simon Roed
    Commented Oct 28, 2020 at 18:29
  • 1
    $\begingroup$ I'm not sure in Python because I'm using another programming language but I will provide to you some of the good references which you can model those in your favorite language. đź‘Ťđź‘Ť $\endgroup$
    – A.Omidi
    Commented Oct 29, 2020 at 7:08
  • 1
    $\begingroup$ In the first, would you see this and this links to introduce some of the good examples in the parallel scheduling. One is in python. Also, there is a good academic/practical software so-called Lekin. I recommended you try that. For your last question, I think you can capture it by introducing an auxiliary binary variable / a specific set by performing a filter on the model constraints. $\endgroup$
    – A.Omidi
    Commented Oct 30, 2020 at 11:34

1 Answer 1

Reset to default
2
$\begingroup$

It is an unrelated parallel machine scheduling problem with sequence-dependent family setup times. The tools define the families; the materials are family members. The tool that is on a machine completely defines the state of the machine. In the machine scheduling literature the problem might be denoted as Q|sij|Cmax

It's unrelated parallel machines because not all families can be installed on all machines. A special case though, where processing time of task $j$ on machine $k$ is either $p_j$ or infinite-ish.

Not really sure what the state of the art is for Q|sij|Cmax but the simpler uniform parallel machine problem P|sij|Cmax isn't super rare in the literature.

A quirk you have to deal with (i.e. side constraint) is that your tool count is limited so a family can only be on a limited number of machines at a time. The underlying problem remains Q|sij|Cmax but your problem has this additional difficulty.

I suggest that you'd use a list scheduling heuristic here as your starting point...

Improve this answer
$\endgroup$
4
  • $\begingroup$ Do you have a link to some good resources about this problem? Possibly also some examples coded in python? $\endgroup$
    – Simon Roed
    Commented Oct 28, 2020 at 18:28
  • $\begingroup$ What happens to the the type of problem if all tools can be placed in all machines? What type of problem is it then? and do you have resources for that type of problem as well? $\endgroup$
    – Simon Roed
    Commented Oct 29, 2020 at 14:26
  • 1
    $\begingroup$ If all tools can go on all machines, whether the machines are uniform, related or unrelated depends on how the same jobs' processing times differ across machines. Uniform means the processing time for any given job $j$ is the same on all machines; Related they differ for $j$ by constant factors; Unrelated means the time to do $j$ on one machine or another has a more complex relationship. The original problem posed here has a certain form of Unrelated. $\endgroup$
    – the lorax
    Commented Nov 5, 2020 at 8:58
  • 1
    $\begingroup$ @SimonRoed to my mind the best book on machine scheduling remains the 1990s book by Lawler, Lenstra, Rinnooy Kan and Shmoys. It is quite dry but nevertheless is a super-solid reference. See research.tue.nl/en/publications/… $\endgroup$
    – the lorax
    Commented Nov 5, 2020 at 9:01

Your Answer

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

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