Dual tasks (DTs) are characterized by the requirement for additional mechanisms that coordinate the processing order of two temporally overlapping tasks. These mechanisms are indicated by two types of costs that occur when comparing DT blocks with fixed and random orders of the component tasks. On a block level, task-order control costs are reflected in increased reaction times (RTs) in random-order compared to fixed-order blocks, indicating global, monitoring-based, coordination mechanisms. On a trial level, within random-order blocks, order-switch costs are indicated by increased RTs on order switch compared to order repetition trials, reflecting memory-based mechanisms that guide task-order in DTs. To test the nature of these mechanisms in two experiments, participants performed DTs in fixed- and random-order blocks. In random-order blocks, participants were either instructed to respond to both tasks according to the order of task presentation (sequential-order instruction) or instructed to freely decide in which order to perform both tasks (free-order instruction). As a result of both experiments, we demonstrated that task-order control costs were reduced under the free-order compared to the sequential-order instruction, whereas order-switch costs were not affected by our instruction manipulation. This pattern of results suggests that the task-order control costs reflect global processes of task-order regulation such as engaging monitoring processes that are sensitive to changes in order instructions, while order-switch costs reflect rather local memory-based mechanisms that occur irrespective of any effort to coordinate task-order.