Dynamic heuristics for the generalized job-shop scheduling problem
Authors:
- 1 October 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1062922X,p. 2562-2567
Abstract
This paper proposes to solve the generalized job-shop scheduling problem by using several original static and dynamic heuristics relying on the machines' potential load. We consider a generalized job-shop problem with unrelated parallel machines which can process the operations of the different jobs and, moreover, any precedence constraints between the operations are allowed. The objective is to minimize the completion date of all the jobs (makespan). This problem is NP-hard. Experimental results using various important randomly generated benchmarks are satisfactory and promising.Keywords
This publication has 19 references indexed in Scilit:
- Parallel Machine Scheduling (PMS) in Manufacturing Systems Using the Ant Colonies Optimization Algorithmic RuleJournal of Applied Sciences, 2007
- Duality-Based Algorithms for Scheduling Unrelated Parallel MachinesINFORMS Journal on Computing, 1993
- Job Shop Scheduling with Tooling Constraints: a Tabu Search ApproachJournal of the Operational Research Society, 1991
- Analysis of a linear programming heuristic for scheduling unrelated parallel machinesDiscrete Applied Mathematics, 1985
- Recent Developments in Deterministic Sequencing and Scheduling: A Survey1982
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979
- Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical ProcessorsJournal of the ACM, 1977
- Centralized Scheduling and Priority Implementation Heuristics for a Dynamic Job Shop ModelA I I E Transactions, 1977
- A Survey of Scheduling RulesOperations Research, 1977
- Exact and Approximate Algorithms for Scheduling Nonidentical ProcessorsJournal of the ACM, 1976