I thought about solving a Job-shop problem with gradient descent. My idea is the following: solve a related, continuous problem, where each machine can work multiple jobs at the same time, then in the end try to find a discrete solution with the continuous solution as guidance.
For the continuous problem, I give each machine for each day a ressource vector (non-negative entries summing up to one) of how much hours should be spent on which job, and the hours are assumed to be spread out over the day evenly. So if e.g. jobs $J,J_1,J_2$ take $8$ hours each, $[1,2,1]$ hours have already been invested and the machine runs for $4$ hours with the ressource vector $[0,0.25.0.75]$, in the end $J$ has $8-1=7$ hours left, $J_1$ has $8-2-0.25\cdot4=5$ hours left and $J_2$ has $8-1-0.75\cdot 4=4$ hours left. If a job is already finished or still locked (because another job has to be finished first), its value in the ressource vector is set to $0$ and the other values scaled up accordingly.
So given ressource vectors for $n$ days, I can compute how much of each job is left to do, or when a given job was finished (as a real number, i.e. if a job has $2$ hours left at the end of day $k$ and the machine spends $4$ hours on it at day $k+1$ then the job finishes at day $k+1/2$). If the jobs have individual deadlines, I can compute a loss function where a job ending before its deadline contributes positively while a job ending after its deadline contributes negatively.
This value (in dependence of the ressource vectors) should be piecewise linear, so differentiable almost everywhere, except for the cases where a job finishes exactly at the end of the day.
For translating back to the discrete case, I thought about some kind of greedy algorithm which selects the next job in a way to minimize the difference between the discrete and the continuous solution at the given time.
Does it make sense to run gradient descent on this problem?