I've looked into numerous solutions for the simple version of this problem, but I've found no solutions for advanced cases, short of sorting through all possible permutations.
I don't know where to begin this question, but I'll do my best.
In my case, this will be in reference to a machine shop.
In order to run a part through a set of procedures using a cnc machine, the machine must first go through a setup process. This time varies depending on what type of part was run last.
Lets say widget A requires tools 1 and 2 to be put on the machine. There were no previous tools on the machine and each tool requires a minute for it to be install correctly. This means that widget A requires a 2 minute setup time. Now, lets say widget B requires tools 3 and 2. In this case, since tool 2 can be used again, it only requires 2 tool changes (removing tool 1 and installing tool 3).
Next, you have the process time that the part actually requires to be build on the respective machine. In most machine shops, this varies depending on what machine it's being run on.
Then you have constraints like the date that a part is required by and weights to certain jobs (if a job is flagged as "rush", its requirements are weighted higher than similar orders).
Luckily, in my case, I have the majority of this data. My system has collected the time a machine takes to build a specific part as well as the setup time required between different parts. The reason I'm looking into a programmatic way of optimizing this schedule is because there are thousands of different parts and it requires a full time worker with extreme knowledge of the shop to schedule days out. Even then, calculating lead time is a nightmare and it's just a ballpark estimation in the end.
I'm curious if anyone here has dealt with similar issues and could point me to some research material that I might find interesting.
I know this is cobbled together, so I'd gladly answer any queries for additional information.