Scheduling open shops with unit execution times to minimize functions of due dates. (English) Zbl 0652.90063

Liu, C. Y.; Bulfin, R. L.

Oper. Res. 36, No. 4, 533-559 (1988).

We examine the problem of scheduling n jobs, each of which must be processed by m machines. If the order in which a given job is processed on the machines is not fixed, the system is called an open shop. This situation might occur in testing components of an electronic system or doing repair work on an automobile. The computational difficulty of solving most open shop problems is known, with the majority being NP- hard. The computational difficulty of a few special cases is unknown, most notably when the jobs have identical processing time and the measure of performance is a function of job due dates. We reduce this uncertainty by developing polynomial algorithms to minimize the total tardiness and the number of tardy jobs in an open shop with identical processing time jobs.

MSC:

90B35	Deterministic scheduling theory in operations research
68Q25	Analysis of algorithms and problem complexity

Keywords:

scheduling n jobs; m machines; open shop; polynomial algorithms; total tardiness; identical processing time jobs