Scheduling Jobs on Several Machines with the Job Splitting Property

ABSTRACT: This scheduling model is derived from the real problem of scheduling looms in a textile industry. Jobs may be independently split over several specified machines and preemption is allowed. Dead-lines are specified for each job and jobs are assumed to be available. It is shown that minimizing maximum weighted tardiness can be done in polynomial time. The case of uniform machines (as in the considered application) can be modeled as a network flow and minimization of maximum tardiness can be done in strongly polynomial time. The case of unrelated machines can be solved either by generalized flow tech-niques or by Linear Programming. Attention is also focused on the problem of finding so-called Unordered Lexico Optima, in order to schedule non-binding jobs as early as possible. This paper deals with a scheduling problem that arises in the production of different types of fabric in a textile industry. The problem is characterized by the presence of several machines (the looms) on which several jobs have to be processed (the articles to be woven). Each job is associated to a definite subset of compatible machines on which it can be processed. A peculiar feature of the problem is that each job can be split arbitrarily and processed independently on these machines. Preemption is also allowed. Each job has a deadline and the objective is to minimize the maximum tardiness or the maximum weighted tardiness in case the jobs have been assigned different weights