O problema vem do bloqueio compartilhado. Por padrão, o método createJobExecution é executado dentro da transação com nível de isolamento serializável. Quando este nível de isolamento é usado, o InnoDB converte implicitamente todas as instruções SELECT simples para SELECT ... LOCK IN SHARE MODE. Portanto, JOB_INST_UN é compartilhado bloqueado devido à consulta na tabela de instâncias. E então, ao inserir a instância do job, é necessário um bloqueio exclusivo em JOB_INST_UN. Deadlock apareceu, se este índice exclusivo foi bloqueado compartilhado por outra transação.