Source author record

Wieslaw Kubiak

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Data Structures and Algorithms math.CO Computational Complexity Computer Science and Game Theory math.OC

Catalog footprint

Research overview

7works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the complexity of open shop scheduling with time lags

The minimization of makespan in open shop with time lags has been shown NP-hard in the strong sense even for the case of two machines and unit-time operations. The minimization of total completion time however has remained open for that case though it has been shown NP-hard in the strong sense for weighted total completion time or for jobs with release dates. This note shows that the minimization of total completion time for two machines and unit-time operations is NP-hard in the strong sense which answers the long standing open question.

preprint2020arXiv

On a Conjecture for a Hypergraph Edge Coloring Problem

Let $H =(\mathcal{M} \cup \mathcal{J} ,E \cup \mathcal{E})$ be a hypergraph with two hypervertices $\mathcal{G}_1$ and $\mathcal{G}_2$ where $\mathcal{M} =\mathcal{G}_{1} \cup \mathcal{G}_{2}$ and $\mathcal{G}_{1} \cap \mathcal{G}_{2} =\varnothing$ . An edge $\{h ,j\} \in E$ in a bi-partite multigraph graph $(\mathcal{M} \cup \mathcal{J} ,E)$ has an integer multiplicity $b_{j h}$ , and a hyperedge $\{\mathcal{G}_{\ell } ,j\} \in \mathcal{E}$ , $\ell=1,2$ , has an integer multiplicity $a_{j \ell }$ . It has been conjectured in [5] that $χ\prime (H) =\lceil χ\prime _{f} (H)\rceil$ , where $χ\prime (H)$ and $χ\prime _{f} (H)$ are the edge chromatic number of $H$ and the fractional edge chromatic number of $H$ respectively. Motivation to study this hyperedge coloring conjecture comes from the University timetabling, and open shop scheduling with multiprocessors. We prove this conjecture in this paper.

preprint2017arXiv

Shared multi-processor scheduling

We study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job's completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized schedules that complete each job at the same time on its private processor and shared processors, if any is actually used by the job, include optimal schedules. We prove that the problem is NP-hard in the strong sense for jobs with arbitrary weights, and we give an efficient, polynomial-time algorithm for the problem with equal weights.

preprint2017arXiv

Shared processor scheduling

We study the shared processor scheduling problem with a single shared processor where a unit time saving (weight) obtained by processing a job on the shared processor depends on the job. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an $O(n \log n)$ optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights --- this instance generalizes the unweighted case of the problem. This algorithm also leads to a $\frac{1}{2}$ -approximation algorithm for the general weighted problem. The complexity of the weighted problem remains open.

preprint2015arXiv

Structural Properties of an Open Problem in Preemptive Scheduling

Structural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on `shifts', i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. So far only rough bounds for these parameters have been derived for specific problems. This paper sharpens the bounds on these structural parameters for a well-known open problem in the theory of preemptive scheduling: Instances consist of in-trees of $n$ unit-execution-time jobs with release dates, and the objective is to minimize the total completion time on two processors. This is among the current, tantalizing `threshold' problems of scheduling theory: Our literature survey reveals that any significant generalization leads to an NP-hard problem, but that any significant simplification leads to tractable problem. For the above problem, we show that the number of preemptions necessary for optimality need not exceed $2n-1$ ; that the number must be of order $Ω(\log n)$ for some instances; and that the minimum shift need not be less than $2^{-2n+1}$ . These bounds are obtained by combinatorial analysis of optimal schedules rather than by the analysis of polytope corners for linear-program formulations, an approach to be found in earlier papers. The bounds immediately follow from a fundamental structural property called `normality', by which minimal shifts of a job are exponentially decreasing functions. In particular, the first interval between a preempted job's start and its preemption is a multiple of 1/2, the second such interval is a multiple of 1/4, and in general, the $i$ -th preemption occurs at a multiple of $2^{-i}$ . We expect the new structural properties to play a prominent role in finally settling a vexing, still-open question of complexity.

preprint2013arXiv

Minimum length path decompositions

We consider a bi-criteria generalization of the pathwidth problem, where, for given integers $k,l$ and a graph $G$ , we ask whether there exists a path decomposition $\cP$ of $G$ such that the width of $\cP$ is at most $k$ and the number of bags in $\cP$, i.e., the \emph{length} of $\cP$, is at most $l$ . We provide a complete complexity classification of the problem in terms of $k$ and $l$ for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to $k$ , we prove that the generalized problem is NP-complete for any fixed $k\geq 4$ , and is also NP-complete for any fixed $l\geq 2$ . On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph $G$ and integers $k\leq 3$ and $l>0$ , constructs a path decomposition of width at most $k$ and length at most $l$ , if any exists. As a by-product, we obtain an almost complete classification of the problem in terms of $k$ and $l$ for connected graphs. Namely, the problem is NP-complete for any fixed $k\geq 5$ and it is polynomial-time for any $k\leq 3$ . This leaves open the case $k=4$ for connected graphs.

preprint2013arXiv

On Transshipment Games with Identical Newsvendors

In a transshipment game, supply chain agents cooperate to transship surplus products. This note studies the effect of size of transshipment coalitions on the optimal production/order quantities. It characterizes these quantities for transshipment games with identical newsvendors and normally distributed market demands. It also gives a closed form formula for equal allocation in their cores.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.