| Recently, family scheduling problems have attracted several researchers because of its real-life applications. The family scheduling problems involve multiple job types where jobs are classified into specific families by their similarity characteristics. Setup occurs only when the two consecutive jobs are from different families. An example of application of family scheduling problems is the colored plastic injection machine. Changing from one color to another color requires a setup. The purpose of this research is to implement methodologies to minimize total tardiness on single machine problems. However, the complexity of the proposed problem is NP-Hard. Seeking for optimal solutions for large problem sizes within a reasonable time is quite questionable. Therefore, this research aims to implement good heuristics that could provide good solutions within a reasonable time.; This research can be divided into two main parts: problems with sequence independent setups and problems with sequence dependent setups. Integer programming models for both problems are proposed in this research. In case of problems with sequence independent setups, three constructive heuristics and five improving heuristics are proposed. The constructive heuristics are implemented to provide initial sequences for improving heuristics.; In case of problems with sequence dependent setups, a hybrid genetic algorithm (HGA) is presented. The implementation of the proposed HGA is discussed thoroughly in this study. Furthermore, the proper genetic algorithm settings, such as crossover probability and population size, can enhance the performance of the algorithm. Thus, prior to investigating the performance of the proposed HGA, a pilot study is performed to determine proper genetic algorithm values.; Experiments for each problem can be divided into two parts: experiments with small problem sizes, and experiments with large problem sizes. In the case of experiments of small problem sizes, the solutions of heuristics/HGA were compared with the solutions from CPLEX solver. In the experiments of large problem sizes, the solutions of heuristics/HGA were compared among each other. Furthermore, nonparametric tests, such as the Friedman tests and Kruskal-Wallis tests, were performed to investigate the effect of parameters, such as number of jobs and number of families, on the performance of heuristics/HGA. |
