Search

We derive an index priority rule for an m-machine no-wait flow shop with the minimum makespan objective and specially-structured job processing times. Our rule generalizes the previously known rules for two special cases of the problem. We also derive an index priority rule for a two-machine no-wait flow shop with the minimum weighted total job completion time objective when all jobs have the same processing time on the first machine. We then show that additional index priority rules can be derived for the latter problem with other scheduling objectives. Finally, we discuss extensions to flow shops with blocking and no-wait job shops and open shops.

We consider the ordered and the proportionate flow shop with unequal machine speeds.We consider both the Cmax and the j=1nCj objectives.We show that permutation schedules are dominant for Cmax with V-shaped speeds.We show that permutation schedules are dominant for j=1nCj with three stages.

We consider job selection problems in shops with ordered machines.We solve the open shop problem in polynomial time.We show that the job shop problem is ordinary NP-hard.We consider the flow shop problem with the total job completion time objective. We consider job selection problems in two-stage flow shops, open shops and job shops. The objective is to select the best job subset with a given cardinality to minimize either the total job completion time or the maximum job completion time (makespan). An O ( n 2 ) algorithm is available for the two-stage flow shop with ordered machines and the minimum makespan objective; we utilize this algorithm to solve the same problem for the total job completion time objective. We then propose an O ( n 1 ) algorithm for the two-machine open shop job selection problem with ordered machines and the minimum makespan objective. We also consider a two-machine job shop in which the first operation of each job is no longer than the second one. We show that the job selection problem in this job shop with the minimum makespan objective is ordinary NP-hard and that the problem becomes solvable in O ( n log n ) time with the additional assumption of ordered jobs.

We consider the single-machine maximum earliness problem with rejection.We present an O(nlogn) algorithm for the problem.We consider the single-machine total earliness problem with rejection.We present a pseudo-polynomial time algorithm for the problem. We present optimal algorithms for single-machine scheduling problems with earliness criteria and job rejection and compare them with the algorithms for the corresponding problems with tardiness objectives. We present an optimal O(nlogn) algorithm for minimizing the maximum earliness on a single machine with job rejection. Our algorithm also solves the bi-criteria scheduling problem is which the objective is to simultaneously minimize the maximum earliness of the scheduled jobs and the total rejection cost of the rejected jobs. We also show that the optimal pseudo-polynomial time algorithm for the total tardiness problem with job rejection can be used to solve the corresponding total earliness problem with job rejection.