An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan

DOI10.1007/S10878-015-9974-7MaRDI QIDQ511693zbMATH OpenOpenAlexFDO

Authors Manzhan Gu, Jinwei Gu, Xiwen Lu

Publication date 22 February 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-015-9974-7

zbMATH Keywords

makespanjob shopavailable constrainbatch machineflexible machine

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan
• Flexible open shop scheduling problem to minimize makespan
• Two-stage flow-open shop scheduling problem to minimize makespan
• Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem
• An algorithm for flow time minimization and its asymptotic makespan properties

Cites work

• A Fluid Heuristic for Minimizing Makespan in Job Shops
• A fluid approach to large volume job shop scheduling
• A simplex based algorithm to solve separated continuous linear programs
• An algorithm for the maximum revenue jobshop problem
• Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines
• Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing
• Efficient Algorithms for Separated Continuous Linear Programs: The Multicommodity Flow Problem with Holding Costs and Extensions
• From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective
• From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective
• Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem
• On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions
• Scheduling jobshops with some identical or similar jobs
• The Complexity of Flowshop and Jobshop Scheduling
• The expected asymptotical ratio for preemptive stochastic online problem

Cited in

(4)

• A prediction based iterative decomposition algorithm for scheduling large-scale job shops
• A hybrid fluid master–apprentice evolutionary algorithm for large-scale multiplicity flexible job-shop scheduling with sequence-dependent set-up time
• Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan
• Minimizing L _max for large-scale, job-shop scheduling problems

This page was built for publication: An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511693)