The single machine parallel batch problem with job compatibility is considered to minimize makespan, where the job compatibility constraints are represented by a graph G. This problem is proved to be NP-hard. And when...The single machine parallel batch problem with job compatibility is considered to minimize makespan, where the job compatibility constraints are represented by a graph G. This problem is proved to be NP-hard. And when the graph G is limited to be a general bipartite, a complete bipartite and a complete m-partite graph, these problems are solved in polynomial time respectively.展开更多
In this paper, we first consider the position restriction scheduling problems on a single machine. The problems have been solved in certain special cases, especially for those obtained by restricting the processing ti...In this paper, we first consider the position restriction scheduling problems on a single machine. The problems have been solved in certain special cases, especially for those obtained by restricting the processing time pj = 1. We introduce the bipartite matching algorithm to provide some polynomial-time algorithms to solve them. Then we further consider a problem on unrelated processors.展开更多
文摘The single machine parallel batch problem with job compatibility is considered to minimize makespan, where the job compatibility constraints are represented by a graph G. This problem is proved to be NP-hard. And when the graph G is limited to be a general bipartite, a complete bipartite and a complete m-partite graph, these problems are solved in polynomial time respectively.
文摘In this paper, we first consider the position restriction scheduling problems on a single machine. The problems have been solved in certain special cases, especially for those obtained by restricting the processing time pj = 1. We introduce the bipartite matching algorithm to provide some polynomial-time algorithms to solve them. Then we further consider a problem on unrelated processors.
