Operation　management　of　automated　storage　and　retrieval　system　(AS/RS)　has　a　great　impact　on　system　performance　and　is　a　hot　research　topic.　Most　existing　works　for　AS/RS　operation　management　address　determining　storage　and　retrieval　(S/R)　machine　sequence　and　minimizing　its　travel　time.　In　the　paper,　we　study　a　new　bi-objective　S/R　machine　sequencing　problem　with　task　release　time　and　due　date　in　a　two-depot　AS/RS.　The　objective　is　to　minimize　the　total　travel　time　of　the　S/R　machine　and　the　total　tardiness　simultaneously.　For　the　problem,　a　new　bi-objective　mixed　integer　linear　programming　model　is　established.　Based　on　problem　property　analysis,　an　exact　ϵ-constraint　method,　a　non-dominated　sorting　genetic　algorithm　II　and　a　promising　heuristic　are　devised　for　the　problem.　Especially,　the　computational　results　show　the　efficiency　and　effectiveness　of　the　proposed　algorithms.　©　2019,　Springer　Science+Business　Media,　LLC,　part　of　Springer　Nature.