Job selection in two-stage shops with ordered machines

• 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(n2)O(n2) 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(n1)O(n1) 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(nlogn)O(nlogn) time with the additional assumption of ordered jobs.