This research considers scheduling problems with jobs which can be divided into sub-jobs and do not required to be processed immediately following one another. Heuristic algorithms considering how to divide jobs are proposed in an attempt to find near-optimal solutions within reasonable run time. The algorithms contain two phases which are executed recursively. Phase 1 of the algorithm determines how jobs should be divided while phase 2 solves the scheduling problem given the sub-jobs established in phase 1. Simulated annealing and genetic algorithms are applied for the two phases and four heuristic algorithms are established. Numerical experiment is conducted to determine the best parameter values for the heuristic algorithms. Examples with different sizes and levels of complexity are generated. Performance of the proposed algorithms is evaluated. It is shown that the proposed algorithms are able to efficiently and effectively solve the considered problems.