Algorithms for minclique scheduling problems

DOI10.1016/S0166-218X(96)00040-6zbMath0872.90048MaRDI QIDQ5961609

Joanna Józefowska, Wiesław X. Kubiak, Bernd Jurisch

Publication date: 25 February 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

tabu searchscheduling problemsnegative weightscomplete weighted graphminimum weighted cliqueself-loopsspectral algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

Machine scheduling with earliness, tardiness and non-execution penalties, Introduction to QUBO, Complexity and Polynomially Solvable Special Cases of QUBO, Fast Heuristics and Approximation Algorithms, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty, Job scheduling methods for reducing waiting time variance, A generic approach to proving NP-hardness of partition type problems, The symmetric quadratic knapsack problem: approximation and scheduling applications, Just-in-Time Scheduling with Equal-Size Jobs, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance, Pseudo-Boolean optimization, Minimization of ordered, symmetric half-products, Positive half-products and scheduling with controllable processing times, On the complexity of the single machine scheduling problem minimizing total weighted delay penalty, FPTAS for half-products minimization with scheduling applications, A clique search problem and its application to machine scheduling, A survey of the state-of-the-art of common due date assignment and scheduling research, Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization, Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product

Uses Software

• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• CON due-date determination and sequencing
• Completion time variance minimization on a single machine is difficult
• New results on the completion time variance minimization
• A projection technique for partitioning the nodes of a graph
• A user's guide to tabu search
• Matrix Analysis
• Minimizing Variation of Flow Time in Single Machine Systems
• Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
• On the Minimization of Completion Time Variance with a Bicriteria Extension
• `` Strong NP-Completeness Results
• State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
• An Algorithm for Partitioning the Nodes of a Graph
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems