Given　a　set　of　time　slots　and　jobs,　each　of　which　has　a　degree　of　parallelism,　an　interval　constraint　(typically　an　arrival　time　and　a　deadline),　and　a　processing　time,　we　consider　the　problem　of　minimizing　the　number　of　machines　for　scheduling　all　the　jobs　while　satisfying　the　constraints.　This　paper　starts　with　a　Linear　Programming　(LP)　formulation　and　argues　that　its　decision　version　is　with　an　integral　polyhedron.　Meanwhile,　we　determine　the　problem’s　feasibility　with　the　LP,　whether　the　given　jobs　can　be　accommodated　by　a　given　number　of　machines　over　allocated　time　slots,　based　on　the　property　of　the　integrality.　Then,　we　show　that　the　feasibility　leads　to　an　LP-based　algorithm,　in　which　the　optimal　solution　can　be　obtained　in　polynomial　time.　Moreover,　our　algorithm　can　also　optimally　compute　a　schedule　to　the　problem　rather　than　merely　determining　the　minimum　number　of　required　machines,　which　compares　favorably　to　the　Earliest　Deadline　First　(EDF)　algorithm　and　the　Least　Laxity　First　(LLF)　algorithm　in　solution　quality.　©　2021,　Springer　Nature　Switzerland　AG.