A preemptive open shop scheduling problem with one resource
A preemptive open shop scheduling problem with nonrenewable resource leads to a problem of the following form. We are given a bipartite multigraph with the property that for all \(i=1,...,n\) and \(j=1,...,m\) there are \(p_{ij}\) parallel edges betweeen i and j. Furthermore there are positive integers \(h_ 1,...,h_ q\) with \(\sum^{q}_{i=1}h_ i=\sum^{n}_{i=1}\sum^{m}_{j=1}p_{ij}\). Find an edge coloring with color sets \(H_ 1,...,H_ q\) such that \[ \sum^{i}_{s=1}| H_ s| \leq \sum^{i}_{s=1}h_ s\text{ for } i=1,...,q. \] It is shown that this problem is NP-complete. For the special case that all \(t_{ij}=1\) necessary and sufficient conditions on the sequence \(h_ 1,...,h_ q\) for the existence of a solution of the problem are given.
- Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
- Restrictions and preassignments in preemptive open shop scheduling
- Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications
- Open shop scheduling with some additional constraints
- On the complexity of preemptive open-shop scheduling problems
- Complexity of a 3-dimensional assignment problem
- scientific article; zbMATH DE number 4095196 (Why is no real title available?)
- scientific article; zbMATH DE number 3325507 (Why is no real title available?)
- scientific article; zbMATH DE number 3338381 (Why is no real title available?)
- Investigations on an edge coloring problem
- Open Shop Scheduling to Minimize Finish Time
- Preemptive scheduling with staircase and piecewise linear resource availability
- Preemptive Scheduling, Linear Programming and Network Flows
- Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
- Minimizing the total completion time in a unit-time open shop with release times
- Survey on fuzzy shop scheduling
- Restrictions and preassignments in preemptive open shop scheduling
- Four decades of research on the open-shop scheduling problem to minimize the makespan
- Bounded colouring motivated by the limited resource partially concurrent open shop problem
- Open shop scheduling problems with conflict graphs
- Scheduling the two-machine open shop problem under resource constraints for setting the jobs
- A job-shop problem with one additional resource type
- Unit-time scheduling problems with time dependent resources
- Compact scheduling of zero-one time operations in multi-stage systems
This page was built for publication: A preemptive open shop scheduling problem with one resource
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2641218)
