A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
The nonpreemptive job shop scheduling problem where \(n\) jobs are to processed on two machines so as to minimize the makespan (maximum completion time) is considered. Job \(i\) consists of \(n_ i\) operations and the sequence of operation processing is given in advance for each job. It is known that the problem is NP-hard for three machines and \(n=3\) and it is polynomially solvable for \(n=2\) and non fixed number of machines. It is known also an \(O(r^ 4)\) algorithm for the problem with two machines and \(n=3\), where \(r\) denotes the maximal number of operations per job. The author proposes an \(O(r^{3k})\) algorithm for the problem with two machines and \(n= k\) (\(k\) is a fixed number). The algorithm can be easily transformed into \(O(r^ 4)\) algorithm for \(n= 3\).
- A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
- A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
- A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing
- An efficient algorithm for the job-shop problem with two jobs
- A polynomial algorithm for multiprocessor scheduling with two job lengths.
- A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint
- On polynomial solvability of two multiprocessor scheduling problems
- A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times
- Algorithms for a two‐machine flowshop problem with jobs of two classes
- On the complexity of two machine job-shop scheduling with regular objective functions
- An efficient algorithm for the job-shop problem with two jobs
- The job shop scheduling problem: Conventional and new solution techniques
- Preemptive job-shop scheduling problems with a fixed number of jobs
- A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
- On the complexity of two machine job-shop scheduling with regular objective functions
- Deterministic job-shop scheduling: Past, present and future
- Shop scheduling problems with multiprocessor tasks on dedicated processors
- An efficient algorithm for a job shop problem
- Complexity of mixed shop scheduling problems: A survey
- Complexity of shop-scheduling problems with fixed number of jobs: a survey
- Low-complexity algorithms for sequencing jobs with a fixed number of job-classes
- scientific article; zbMATH DE number 4131935 (Why is no real title available?)
- scientific article; zbMATH DE number 3970499 (Why is no real title available?)
- scientific article; zbMATH DE number 894722 (Why is no real title available?)
- The Machine Duplication Problem in a Job Shop with Two Jobs
- Job Shop Scheduling With Two Jobs And Nonregular Objective Functions
- An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents
- Two-machine job-shop scheduling with one joint job
- A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
This page was built for publication: A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1326784)
