Job Shop Scheduling

Complexity of value iteration


•	One iteration takes O(\|A\|\|S\|²) time.

•	Number of iterations required :
	poly(\|S\|,\|A\|,1/(1-γ))
•	Overall, the algorithm is polynomial in state
	space, and thus exponential in number of
	state variables.