Abstract
The parallel machine scheduling has been given considerable attention in the past decades. In our dissertation, we study three uniform parallel machine problems with different properties in which the objective is to find a schedule that minimizes the makespan. (1) Due to the global warming effect, how to manage natural resource efficiently and reduce carbon emissions have become important issues. We consider a resource consumption constraint that the total resource consumption cannot exceed a certain amount. For this NP-hard problem, three heuristic algorithms are proposed to generate approximate solutions. Computational results are also provided to demonstrate the performance of the proposed heuristic algorithms (2) Scheduling with learning effects has become a popular topic in the past decade. In classical scheduling, the processing times of jobs are assumed to be fixed and known. However, the skills of workers might be different due to their individual experience. In this problem, the objective is to find not only an optimal schedule but also an optimal assignment of operators to minimize the makespan. Two heuristic algorithms are proposed and the computational experiments are conducted to evaluate their performance. (3) Traditionally, job processing times are assumed to be fixed and known over the entire process. In reality, the job processing times in many situations are not fully known in advance. As a result, fuzzy set theory provides a convenient alternative framework for modeling real-world systems mathematically. We study the parallel machine scheduling problem with fuzzy processing times and learning effects. The objective is to minimize the fuzzy makespan based on the possibility measure. Finally, we proposed two algorithms to solve the scheduling problem.