Using mixed graph coloring to minimize total completion time in job shop scheduling

DOI10.1016/J.AMC.2006.04.063MaRDI QIDQ858768zbMATH OpenOpenAlexWikidataFDO

Authors Fawaz S. Al-Anzi, Ali Allahverdi, George V. Andreev, Yuri N. Sotskov

Publication date 11 January 2007

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2006.04.063

zbMATH Keywords

schedulingbranch and boundjob shoptotal completion timemixed graph coloring

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 1731177
• scientific article; zbMATH DE number 1594564
• A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: a mixed graph coloring approach
• A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring
• Scheduling Problems and Mixed Graph Colorings

Cites work

• scientific article; zbMATH DE number 1731177 (Why is no real title available?)
• A Geometric Model and a Graphical Algorithm for a Sequencing Problem
• A graph coloring algorithm for large scheduling problems
• An efficient algorithm for the job-shop problem with two jobs
• An introduction to timetabling
• Graph colorings with local constraints -- a survey
• Is a unit-job shop not easier than identical parallel machines?
• Mixed graph colorings
• NP-hardness of shop-scheduling problems with three jobs
• Preemptive job-shop scheduling problems with a fixed number of jobs
• Scheduling Problems and Mixed Graph Colorings
• The complexity of shop-scheduling problems with two or three jobs
• Total completion time minimization in two-machine job shops with unit-time operations
• Unit Execution Time Shop Problems

Cited in

(12)

• A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: a mixed graph coloring approach
• scientific article; zbMATH DE number 1594564 (Why is no real title available?)
• Graph coloring approaches for a production planning problem with makespan and setup penalties in a product-wheel context
• Parameterized mixed graph coloring
• Mixed graph edge coloring
• Vyacheslav Tanaev: contributions to scheduling and related areas
• scientific article; zbMATH DE number 7705706 (Why is no real title available?)
• A matrix approach to hypergraph stable set and coloring problems with its application to storing problem
• Fuzzy colouring of fuzzy graphs
• scientific article; zbMATH DE number 1731177 (Why is no real title available?)
• A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring
• Mixed graph colouring as scheduling multi-processor tasks with equal processing times

This page was built for publication: Using mixed graph coloring to minimize total completion time in job shop scheduling

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