Algorithms for generalized nonregular scheduling problems

On-time delivery and meeting due dates are important performance measures in modern production systems. In the machine scheduling literature most studies employ regular objective functions with tardiness penalties to address these goals. There are also studies which consider nonregular objective functions involving penalties for both earliness and tardiness. However, these studies usually address single-machine and parallel machine problems.; In this dissertation we focus on a class of generalized dynamic nonregular scheduling problems in multi-machine production environments. We consider a total weighted earliness and tardiness objective function at the operation level and we allow distinct release times, due dates, and earliness and tardiness penalties for each operation.; This problem is strongly $NP$-Hard, thus any approach for finding an optimal solution is likely to become computationally intractable in most practical situations. We propose and test several heuristics for this problem. We develop an adjacent pairwise interchange neighborhood which is a generalization of a well-known compact search neighborhood for the classical job shop problem. This is an important theoretical development since it establishes a relationship between the regular and nonregular scheduling problems. We propose several other heuristic solution methods including Lagrangian relaxation and local search algorithms with local minima escape mechanisms. We also present a new local search algorithm that combines important features of other well-known local search methods.; We test our heuristics on randomly generated instances of the total weighted earliness and tardiness job shop problem, and on a set of benchmark instances for the total weighted tardiness job shop problem from the literature. We present our computational results and related observations on different solution methods and problem classes. We observe that our heuristic methods produce very good solutions in relatively small CPU times. In particular we find that on the total weighted tardiness job shop problem our heuristics yield results comparable to a state-of-the-art shifting bottleneck procedure from the literature. This is a remarkable finding since our heuristics are designed for a more general class of scheduling problems and do not take advantage of problem structures that are readily available in the total weighted tardiness problems.