A CHROMATIC SCHEDULING MODEL WITH COSTS

An extension of a preemptive open-shop scheduling problem is introduce d. All processing times are integral and in each period i there is a c ost ci for each task which is processed in that period. Finding a sche dule with minimum total cost is shown to be NP-hard; some solvable cas es are discussed; bounds on the cost of an optimum schedule are comput ed. Finally, a special case is studied, namely where each job has at m ost three tasks and each processor has to work on at most three tasks. It is shown to have theoretical complexity equivalent to the general case.