Article ID Journal Published Year Pages File Type
1133418 Computers & Industrial Engineering 2015 4 Pages PDF
Abstract

•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.

Related Topics
Physical Sciences and Engineering Engineering Industrial and Manufacturing Engineering
Authors
, ,