| Scheduling problems exist in various applications in areas of transportation, logistics, manufacturing, and many other service industries. In this thesis, we study both deterministic and stochastic scheduling problems. The thesis consists of three parts.;The second part of the thesis gives an approximation algorithm for a general deterministic complex parallel machine scheduling problem with multiple classes of jobs. This approximation algorithm attempts to generate near-optimal solutions quickly for real-world large-scale scheduling problems.;Finally, the third part of the thesis focuses on multistage stochastic linear programming with recourse. We present a sampling based solution algorithm using a cutting-plane technique. We prove that the algorithm is convergent with probability one under some practical assumptions.;In the first part, we propose a decomposition algorithm for solving exactly a class of hard classical parallel machine scheduling problems. The algorithm is applied to three particular parallel machine scheduling problems. The computational results show that the algorithm is promising and capable of solving large problems in reasonable cpu times. |
