Two machine mixed shop scheduling problem with controllable machine speeds

AbstractThis paper considers a scheduling problem in which the objective is to determine an optimal machine speed pair and an optimal schedule. There are two machines A, B and n jobs each of which consists of two operations. One operation is to be processed on machine A and the other on machine B. The job set consisits of two disjoint subsets F and O. F is a set of flow shop type jobs, while O is a set of open shop type jobs. That is, for each job i in F, processing on A must be completed before processing on B. On the other hand, processing order of each job i in O is not specified and so processing of each job can be started on either machine. Each machine processes at most one job and each job is processed on at most one machine, simultaneously. Further it is assumed that the speed of each machine is controllable.In the situation, the total sum of costs associated with the maximum completion time and machine speeds is to be minimized.The problem is a generalization of two machine mixed shop scheduling problem [6] in a sense that machine speeds are not fixed but variables. For the problem, this paper provides a polynomial time order solution procedure