The no-wait job shop with regular objective: a method based on optimal job insertion

The no-wait job shop problem (NWJS-R) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available.     

On the odd girth and the circular chromatic number of generalized Petersen graphs

A class \(\mathcal{G}\) of simple graphs is said to be girth-closed (odd-girth-closed) if for any positive integer g there exists a graph \(\mathrm {G} \in \mathcal{G}\) such that the girth (odd-girth) of \(\mathrm {G}\) is \(\ge g\). A girth-closed (odd-girth-closed) class \(\mathcal{G}\) of graphs is said to be pentagonal (odd-pentagonal) if there exists a positive integer \(g^*\) depending on \(\mathcal{G}\) such that any graph \(\mathrm {G} \in \mathcal{G}\) whose girth (odd-girth) is greater than \(g^*\) admits a homomorphism to the five cycle (i.e. is \(\mathrm {C}_{_{5}}\)-colourable). Although, the question “Is the class of simple 3-regular graphs pentagonal?” proposed by Ne?et?il (Taiwan J Math 3:381–423, 1999) is still a central open problem, Gebleh (Theorems and computations in circular colourings of graphs, 2007) has shown that there exists an odd-girth-closed subclass of simple 3-regular graphs which is not odd-pentagonal. In this article, motivated by the conjecture that the class of generalized Petersen graphs is odd-pentagonal, we show that finding the odd girth of generalized Petersen graphs can be transformed to an integer programming problem, and using the combinatorial and number theoretic properties of this problem, we explicitly compute the odd girth of such graphs, showing that the class is odd-girth-closed. Also, we obtain upper and lower bounds for the circular chromatic number of these graphs, and as a consequence, we show that the subclass containing generalized Petersen graphs \(\mathrm {Pet}(n,k)\) for which either k is even, n is odd and \(n\mathop {\equiv }\limits ^{k-1}\pm 2\) or both n and k are odd and \(n\ge 5k\) is odd-pentagonal. This in particular shows the existence of nontrivial odd-pentagonal subclasses of 3-regular simple graphs.     

Total completion time minimization in online hierarchical scheduling of unit-size jobs

This paper investigates an online hierarchical scheduling problem on m parallel identical machines. Our goal is to minimize the total completion time of all jobs. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the first machine and the job with a higher hierarchy can be processed on any one of m machines. We first show that the lower bound of this problem is at least \(1+\min \{\frac{1}{m}, \max \{\frac{2}{\lceil x\rceil +\frac{x}{\lceil x\rceil }+3}, \frac{2}{\lfloor x\rfloor +\frac{x}{\lfloor x\rfloor }+3}\}\), where \(x=\sqrt{2m+4}\). We then present a greedy algorithm with tight competitive ratio of \(1+\frac{2(m-1)}{m(\sqrt{4m-3}+1)}\). The competitive ratio is obtained in a way of analyzing the structure of the instance in the worst case, which is different from the most common method of competitive analysis. In particular, when \(m=2\), we propose an optimal online algorithm with competitive ratio of \(16\) \(/\) \(13\), which complements the previous result which provided an asymptotically optimal algorithm with competitive ratio of 1.1573 for the case where the number of jobs n is infinite, i.e., \(n\rightarrow \infty \).     

‘Strong Personalities’ and ‘Strong Institutions’ Mediated by a ‘Strong Third Force’: Thinking ‘Systems’ in Corruption Control

Corruption in public sector is a complex, ‘messy’ and ‘fuzzy’ phenomenon which involves calculus machinations between actors and constantly growing in sophistication. Consequently, an attempt to prevent, control or fight it requires systems thinking that ranges from public officials with integrity and personal ethics [strong personalities]; administrative rules and procedures as well as governments adopting, enforcing and monitoring appropriate systems [strong institutions]. This paper provides a systems approach to enhancing public sector ethics through ‘a corruption control tripod’ in preventing, controlling and combating corruption in all its forms. This framework discusses three overarching pillars and argues that adopting a reductionist approach in corruption control would yield futility; there is a need for synthesis so that each one would reinforce the other.     

Strategic Planning in the Malawi Public Sector: Potential Tool for Progress or Regression?

The process of developing strategic plans in the public sector is regarded as one indicator of positive reform in the system. The assumption is that strategic planning ensures that (just like in the private sector) public sector organizations’ operations should cost less but deliver better service. Ultimately the argument is that public sector institutional governance and responsiveness to the citizenry is not only seen but felt. However, strategic planning has to be done in an appropriate manner for it to deliver. For instance an analysis of the underlying motives, the role of leadership in the process as well as the relevance or viability of the guiding strategic planning model significantly affect the nature of expected results. In the early 2000s, the Malawi public sector embarked on a serious drive towards strategic planning process as part of its reform package. In order to ascertain it’s potential to transform the Malawi public service, this paper focuses at critically analyzing the strategic planning process in the Malawi public sector by among other things asking: who initiated and led the process? What approach determined the process? What is the possible potentiality of the adopted strategic planning approach in enhancing the reform agenda in Malawi? Based on interviews with senior officers in key Malawi public sector institutions, the paper concludes that the strategic planning process is ‘transitional and fluid’ hence lacks the clout to effectively enhance reforms in this sector. Another finding is that lack of effective leadership has largely contributed to the status quo.     

Lust an der Macht – Frauen in Organisationen

Storyline and analysis of the film “The Devil Wears Prada” provide vivid scenes to derive reflections on organisational culture in globalised companies and women in chief positions. Women come into conflict with leading the company successfully, the dependence on efficient – female – staff and the image as a woman. The article illustrates, how influences of the company’s products fashion und fashion market have a normative effect, especially on female staff members. Theories of organisational culture, careers of women and findings of gender research are shown in connection with complex strategies of women in their determination to succeed, to self-realization and the pressure to adapt oneself. This involves reflected perspectives to leave clichés of gender and to reinforce organisational and personal potentials.     

Arbeitszufriedenheit und Energie

Focussing on energy as a highly activated affective state offers new opportunities to promote well-being at work and job performance. In this paper, I will describe current research on recovery, affective work events and characteristics of work tasks linked to energy. The practical implications for promoting energy at work are discussed.     

Minimizing the number of tardy jobs in two-machine settings with common due date

We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity \(O(p(n) \times \sqrt{2}^n)\), p being a polynomial function of n.     

The thickness of the complete multipartite graphs and the join of graphs

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is known for relatively few classes of graphs, compared to other topological invariants, e.g., genus and crossing number. For the complete bipartite graphs, Beineke et al. (Proc Camb Philos Soc 60:1–5, 1964) gave the answer for most graphs in this family in 1964. In this paper, we derive formulas and bounds for the thickness of some complete k-partite graphs. And some properties for the thickness for the join of two graphs are also obtained.     

Parameterized algorithms for min–max 2-cluster editing

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).