In this thesis, we address the single machine scheduling which is a very fundamental scheduling prob- lem with extensive applications in various areas ranging from computer science to manufacturing. Also, this problem is the building block of different decomposition-based algorithms for shop scheduling prob- lems. We design a parallel randomized approximation algorithm for the non-preemptive single machine scheduling problem with release dates and delivery times, where the objective is to minimize the completion time of all jobs (i.e., makespan). We employ the proposed approximation algorithm to design efficient parallel algorithms for flow shop scheduling problem. In this thesis, our aim is to leverage the huge amount of computing power of the current multicore computing systems and develop efficient parallel algorithms to solve large size flow shop scheduling problems in reasonable amount of time. We design two parallel algorithms based on the Shifting Bottleneck (SB) heuristic. The first one is a coarse-grained parallel algorithm that is suitable for execution on multi-core systems with a small number of cores, while the second one is a fine-grained parallel algorithm suitable for multi-core systems with a large number of cores. We perform extensive experimental analyses to evaluate the performance of the proposed algorithms for instances of various sizes.