We study a basic scheduling problem arising in the area of manufacturing design and plan merging in AI. In its most simple form, there is a set of tasks that need to be scheduled on a collection of machines. These tasks have precedence constraints, and each task can be executed only on a specified subset of the machines. Furthermore, each machine has a loading time that is incurred only for the first task executed on that machine in a single run. The objective is to minimize the makespan. We show that even simpler version of this problem are NP-hard (also MAX SNP-hard) and we study a variety of heuristics for obtaining sub-optimal solutions. We are also able to establish hardness results on the approximability of these scheduling problems. Our approximation technique extends to solving another scheduling problem that arises in the context of compilers for parallel machines. (Joint work with Samir Khuller (Maryland) and Seffi Naor (Technion). Scheduled to appear in FOCS 95)