We consider the sequencing of N jobs on a deteriorating flexible machine with a limited tool-magazine capacity. Each job has its own processing time, tool requirements, and processing complexity. As the jobs are processed, machine down-time may be caused by tool-magazine switches or machine repairs (preventive maintenance or unexpected machine failures). In this paper, we address minimization of such machine down-time, and develop optimal algorithms for three different application scenarios of the job and tool scheduling problem in a flexible machine. While the first two scenarios do not consider preventive maintenance scheduling, the third scenario does so explicitly.