Solving a Scheduling Problem with MATLAB

Hello together,

I'm trying to solve a scheduling problem using Matlab, but haven't found the right approach yet. Here is an abstract example of the problem:

There are three different machines and two jobs to be done.

The schedule for job 1 is 4 time units in machine A and 8 time units in machine B.

The schedule for job 2 is 4 time units in machine A and 4 time units in machine C.

Now the challenging part is that there is one robot that transfers the jobs. The robot is blocked one time unit before and after a job transfer. The jobs in sequential order are visualized in the following gantt chart:

The idea is that each process can be extended, which gives the opportunity to overlap the two jobs. (Which is not possible if the process times are fixed)

My goal is to find the optimal configuration of job starts and durations that minimize the total process time without double occupying a machine or the robot. The solution to the example mentioned above would be to prolong the period of job 1 in machine C by one time unit, as shwon in the following gantt chart:

My first idea was to use linear programming and and the linprog function of the optimization toolbox. I also managed to solve the problem this way. However, I needed to manually distinguish many different cases, since depending on the process order, different constraints need to be considered. This approach is very time consuming and I'm pretty sure the must be a more efficient way.

Does anyone know a better approach to solve this problem?

Many thanks in advance!

Jan