We propose a method to solve scheduling problems taking into account energy-efficiency and variable speeds. We focus on a scheduling problem for autonomous micro-ferries, where the task of assigning transportation requests to specific micro-ferries and determining the order of handling them is done centrally. The method is based on the travelling salesman problem and vehicle routing problem with time-windows, but differs in the inclusion of constraints on the energy-consumption and an increased flexibility in travel times, which are both influenced by varying the speed of the micro-ferries. This results in a mixed-integer non-linear programming problem, which can be transformed into a mixed-integer linear programming problem by using an approximation of the speed variables.