We consider an open-shop problem: n jobs have to be processed on m machines where each machine can process at most one job at a time and each job can be processed on at most one machine at a time. The processing times for all operations are given. Preemptions are allowed, that means each operation can be stopped and continued later on. The order of machines for job Ji is called machine order of job Ji, the order of jobs on machine Mj is called job order on machine Mj. In the case of an open-shop problem all machine orders and job orders have to be determined in such a way that the average completion time is minimized. New models of scheduling problems with preemption are presented which base on models for problems without preemption. Because the considered problem is NP-hard, lower bounds and heuristics are developed. Computational experiments demonstrate the quality of the algorithms. For small numbers of jobs and machines the obtained results are also compared with the optimal solutions determined by an exact algorithm.
