In planning and scheduling domains such as space-based data collection, task execution cost is highly dependent on system state. Transitioning between states may also be costly. In this paper we consider the problem of scheduling tasks in the case where the cost of executing a task depends upon the state in which it is executed. To separate out the state-dependent aspects of the question, we examine several simplified versions of the problem in which we consider the interactions of task execution cost and state transition cost without the complications introduced by task dependencies and preconditions. We then describe a solution by exhaustive search. Finally, we outline a promising line of research involving a statistical analysis of the manner in which task execution cost depends on state.