Voici comment je l'ai fait (MySQL 5.0.45) :
ALTER TABLE `job_dependency`
ADD FOREIGN KEY (`job`) REFERENCES `job` (`id`),
ADD FOREIGN KEY (`dependency`) REFERENCES `job` (`id`);
Il y a des problèmes avec ON DELETE CASCADE dans cette situation, alors ne l'utilisez pas.