機械の取替時間を考慮する機械スケジューリング問題は，順序制約を持つ作業から構成される仕事の集合，各作業を処理可能な機械の集合および機械を替えるときの取替時間が与えられるとき，すべての仕事を処理し，最大完了時刻（メイクスパン）を最小にするスケジュールを求める問題である．この問題は，生産計画やサプライチェーンなど実社会の様々な課題への応用に繋がる．本研究では，まず仕事が1つだけのとき，多項式時間で最適なスケジュールが求められることを示す．さらに，問題の性質を利用し，効率的に実現する手法も提案する．次に，仕事が3つと機械が2台のとき，動的計画法を提案する．