Three essays in scheduling

This dissertation contains three distinct but related essays in the area of machine-scheduling. In the first essay, we consider an economic lot sizing problem (ELSP) on multiple, parallel, and identical machines having setup constraints. The problem assumes that no stock-outs are allowed; and machine interferences, the unavailability of a machine when a production request is initiated, is explicitly considered. We demonstrate a new methodology for decomposing the ELSP problem into two problems: (a) assignment and lot sizing problem on multiple identical machines, and (b) development of a job sequence using reorder points. The assignment problem is initially formulated as a nonlinear program. We transform this nonlinear program into a binary integer linear program (BILP). We use the BILP to determine the lot sizes. Given the lot sizes, a discrete event simulation model is used to determine reorder points. We provide a numerical example to illustrate the method of solving the ELSP and obtain a feasible solution by decomposition.; In the second essay, we consider the problem of simultaneously scheduling jobs and preventive maintenance on a single machine, for jobs with deteriorating processing times, with an objective of minimizing makespan. The deterioration of a job's processing time depends on the time since the completion of the last preventive maintenance operation (PMO). We develop a mixed-integer programming formulation and prove the NP-Completeness of this problem. Further we present two heuristics to simultaneously determine the number of PMOs, the position of the PMOs, and the job sequences. The performance of the two heuristics is estimated by determining the incremental improvement achieved from the application of a simulated annealing algorithm.; In the third essay, we consider the problem of scheduling jobs and preventive maintenance on a single machine subject to stochastic breakdowns. We consider three different performance measures and show that the introduction of the PMOs makes it hard to obtain closed-form expressions for the job completion times, and hence for the performance measures. Therefore, we develop Monte Carlo simulations to examine the performance of various scheduling strategies known to provide good solutions when PMOs are not allowed.