Minimization of open orders – polynomial algorithms for some special cases

Consider a production system where a batch of tasks have to be performed. Once a task is performed an item type is produced. This item type is required by a client or several different clients. A client order consists of a set of item types, hence, as tasks are performed, some client orders are partially or completely fulfilled. A client order is considered open as soon as the first item type that the client requires is produced. A client order remains opened until the last item type that he/she requires is produced. In this paper we focus on the problem of sequencing the tasks in order to minimize the maximum number of open orders during the production run. Polynomial algorithms are presented for some special cases of the problem, where for each one of the tasks, the items produced belong to at most two different clients.