Parallel machine bicriteria scheduling: Some complexity results and the problem of interfering job sets

Multicriteria scheduling stems from the need to address real-world problems that often involve conflicting objectives. A schedule that optimizes one criterion may perform quite poorly for another. Decision makers must therefore carefully evaluate the trade-offs involved in considering several different criteria.; We consider bicriteria scheduling problems involving classical scheduling objectives on identical, parallel machines with job release dates. The jobs are assumed to have equal processing times. Our main goal in this dissertation is to advance the knowledge of computational complexity of bicriteria problems in this environment; we view our contribution as part of the effort to, in Baptiste's words; "widen the existing frontiers of solvability in polynomial time". Our bicriteria treatment of the problem includes lexicographic optimization, minimization of a composite linear function, generation of schedules on the efficient frontier and the generation of all non-dominated solutions. Using the framework provided by the dynamic program of Baptiste and the linear programming approach of Brucker and Kravchenko, we show the polynomial solvability of several bicriteria problems. The complexity status of these bicriteria problems was unknown before.; Next, we consider bicriteria scheduling on identical parallel machines in a slightly different context: jobs belong to two disjoint sets, and each set has a criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal, in the best case, would be to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT-LPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide reasonable solution qualities and are computationally efficient.