Positive half-products and scheduling with controllable processing times

DOI10.1016/j.ejor.2004.04.012zbMath1066.90031OpenAlexW1978857382WikidataQ57633924 ScholiaQ57633924MaRDI QIDQ1772845

Adam Janiak, Mikhail Y. Kovalyov, Frank Werner, Wiesław X. Kubiak

Publication date: 21 April 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.04.012

zbMATH Keywords

Computational complexityFully polynomial time approximation schemeSingle machine schedulingControllable processing timesPseudo-Boolean optimization

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Complexity and performance of numerical algorithms (65Y20)

Related Items

Optimal testing and repairing a failed series system, A Polytope for a Product of Real Linear Functions in 0/1 Variables, Introduction to QUBO, Fast Heuristics and Approximation Algorithms, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, A survey of scheduling with controllable processing times, Considering manufacturing cost and scheduling performance on a CNC turning machine, Batch scheduling of identical jobs with controllable processing times, Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints, Inverse interval scheduling via reduction on a single machine, Single machine scheduling problem with controllable processing times and resource dependent release times, Pre-emptive scheduling problems with controllable processing times, Min‐sum controllable risk problems with concave risk functions of the same value range, The symmetric quadratic knapsack problem: approximation and scheduling applications, Single machine scheduling with controllable release and processing parameters, A strongly polynomial FPTAS for the symmetric quadratic knapsack problem, Single-machine scheduling with machine unavailability periods and resource dependent processing times, Minimization of ordered, symmetric half-products, Approximation schemes for job shop scheduling problems with controllable processing times, Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications, Just-in-time scheduling with controllable processing times on parallel machines, Scheduling two agents with controllable processing times, SCHEDULING WITH DISCRETELY COMPRESSIBLE RELEASE DATES TO MINIMIZE MAKESPAN, Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling, Differential approximation schemes for half-product related functions and their scheduling applications, Min-max controllable risk problems, FPTAS for half-products minimization with scheduling applications, 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

Cites Work

• Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard.
• Minimization of ordered, symmetric half-products
• New results on the completion time variance minimization
• Minimization of Half-Products
• Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine
• Algorithms for minclique scheduling problems
• Unnamed Item
• Unnamed Item