China
Africa
Explore chapters and articles related to this topic
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
The above reductions do not establish that the open shop problem is NP-hard in the strong sense [30], i.e., the problem is not shown to be NP-hard when the sum of the task times is bounded by a polynomial of n and m. This is because the partition problem is not NP-complete in the strong sense unless P= NP. However, Lenstra [31,32] has shown that the open shop problem is NP-hard in the strong sense for an arbitrary number of machines. To show that this problem is NP-hard in the strong sense we reduce the 3-partition problem to it. In the 3-partition problem we are given m objects and a size or weight function defined as in the partition problem. The problem is to decide if the set of objects can be partitioned in m/3 subsets such that the sum of the size of the objects in each subset is identical. Figure 6.5 gives the architecture of the reduction for the case when m=18. The main idea is to introduce a set of jobs that no matter how they are assigned in a schedule with certain finishing time, there will be m/3 equally sized blocks of idle time on machine M1 whose total size corresponds to the sum of the size of the objects
Decision diagram-based integer programming for the paired job scheduling problem
Published in IISE Transactions, 2020
Leonardo Lozano, Michael J. Magazine, George G. Polak
We first examine the version of the problem that considers the objective of minimizing makespan, denoted by PJSP-M. We define a decision version of the problem, which poses the question: “does there exist a feasible schedule of makespan less than or equal to a given threshold Q?” We refer to this decision problem as PJSP-MD. We analyze the complexity of PJSP-MD using a transformation from the 3-partition problem as described by Garey and Johnson (1979). Consider a set of integers and a value such that and for all The 3-partition problem asks the question: “can we partition into m disjoint three-element sets such that for all ?”