An online algorithm for continuous slab caster scheduling

Lee et al. (Lee, K., Chang, S.Y., and Hong, Y., 2004. Continuous slab caster scheduling and interval graphs. Production Planning & Control, 13 (5), 495–501) have introduced a slab caster scheduling problem and developed an optimal algorithm. Their algorithm is efficient but an offline algorithm that we need the information on all the customer orders a priori to implement. In this article, we propose an online algorithm that we can implement without knowledge of the orders yet to arrive. We show that the offline version of our new algorithm also provides an optimal solution and the online version has the worst case performance ratio of 3. We also give a short proof on the correctness of Lee et al.'s algorithm.     

A re-analysis of the occupational stress indicator

Abstract

This paper investigates the reliability of the Occupational Stress Indicator (OSI). Data from a sample of university staff, drawn from all areas of an urban university, are used to reassess the apparently low reliabilities of many of the OSI subscales reported by Cooper et al. (1988). In addition, factor analysis results are reported for the first time for the sources of pressure data. The reliability data reported here, while higher reliabilities than originally obtained, remain unacceptably low. A lack of stability in the device as it is currently formulated seems apparent. The paper also presents for the first time a detailed analysis of the sources of pressure scale, indicating a solution different from that proposed by Cooper et al. (1988). Certain areas of the OSI clearly need refinement; the inclusion of locus of control and type A behaviour as personality variables in particular is called into question. Observations regarding the particular strengths and weaknesses of this device, and suggestions for future refinements, are offered.     

Note on solving inventory models from operational research view

In this article, we will show that an optimal solution can be derived without complicated mathematical derivation, an improvement on the paper [Yang, G.K., et al., 2011. Note on inventory models with Weibull distribution deterioration. Production Planning & Control, 22 (4), 437–444] that was recently published in Production Planning & Control. We extend their inventory model with a generalised deterioration and backlog rates. Our findings will allow researchers to consider inventory models directly from the view of operational research instead of complex analysis.     

Optimal algorithms for online time series search and one-way trading with interrelated prices

The basic models of online time series search and one-way trading are introduced by El-Yaniv et al. in Algorithmica 30(1), 101–139 (2001) where it is assumed that the prices are bounded within interval [m,M] (0<m<M). In this paper, we consider another case where every two consecutive prices are interrelated, that is, the variation range of each price depends on its preceding price. We present optimal deterministic online algorithms for the two problems, respectively. According to one conclusion in Algorithmica 30(1), 101–139 (2001), we further point out that for the case we considered, an optimal deterministic algorithm for the one-way trading problem can be regarded as an optimal randomized one for the time series search problem, and randomization is useless for the one-way trading problem.     

Multi-item inventory model with quantity-dependent inventory costs and demand-dependent unit cost under imprecise objective and restrictions: A geometric programming approach

A multi-item inventory model with constant demand and infinite replenishment is developed under the restrictions on storage area, total average shortage cost and total average inventory investment cost. These restrictions may be precise or imprecise. Here, it is assumed that inventory costs are directly proportional to the respective quantities, and unit purchase/production cost is inversely related to the demand. Restricted shortages are allowed but fully backlogged. First, the problem is formulated in crisp environment taking the deterministic and precise inventory parameters. It is solved by both geometric programming (GP) and gradient-based non-linear programming (NLP) methods. Later, the problem is formulated with fuzzy goals on constraints and objectives where impreciseness is introduced through linear membership functions. It is solved using the fuzzy geometric programming (FGP) method. The inventory models are illustrated with numerical values and compared with the crisp results. A sensitivity analysis on the optimum order quantity and average cost is also presented due to the variation in the tolerance of total average inventory investment cost and total average shortage cost following Dutta et al., 1993, Fuzzy Sets and Systems, 55, 133-142.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

The optimum traversal of a graph

For a given graph (network) having costs [c_ij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity q_ij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc.     

Scheduling in Switching Networks with Set-Up Delays

We consider the (preemptive bipartite scheduling problem PBS) (Crescenzi et al., On approximating a scheduling problem, Journal of Combinatorial Optimization, vol. 5, pp. 287–297, 2001) arising in switching communication systems, where each input and output port can be involved in at most one communication at the same time. Given a set of communication tasks to be communicated from the transmitters to the receivers of such a system, we aim to find a schedule minimizing the overall transmission time. To achieve this, we allow the preemption of communication tasks. However, in practice preemption comes with a cost, d, and this renders the problem NP-hard (Gopal et al., An optimal switching algorithm for multibeam satellite systems with variable bandwidth beams, IEEE Trans. Commun., vol.30, pp. 2475–2481, 1982). In this paper, we present a approximation algorithm, which is the first one for the PBS problem with approximation ratio strictly less than two. Furthermore, we propose a simple optimal polynomial time algorithm for a subclass of instances of the PBS problem.This work has been partially supported by the the European Union (FET-Working Group APPOL II), and the Greek General Secretariat of Research and Technology.     

On the Sensitivity Analysis of the IIM: A Rejoinder

In this note I reply to the comments by Haimes et al. on my paper on the sensitivity analysis of the inoperability input‐output model. I make the case for a moment‐independent sensitivity analysis.     

Resource smoothing: A cost minimization approach

From the available literature, there seems to be no defined approach to resource smoothing exercise except those attempted by Weist (1967, Management Science, 13, B359-B377) and Burgess and Killebrew (1962, Journal of Industrial Engineering, 13, 76-83). The aim of the smoothing exercise is to achieve optimal resource usage by avoiding high peaks and deep valleys in the project resource profile. The general approach has always been to move some activities with floats in the high peak regions to be started at a later date, and as this is done, the valleys will be filled to smooth the resource profile subject of course to time constraint. If this approach is followed as it is, it would be difficult to determine optimality especially when many resources are involved. A cost minimization approach is envisaged in the present study with no limitation on the number of resource inputs. In a situation where the resources are assumed to have the same value, the cost assigned to each of them should be similar. The method follows the general concept but with a difference; cost of the activity in question is considered. The exercise is continued until all the floats are exhausted. The optimum result would then be the one with the minimum cost profile. From examples used for the evaluation, the results obtained are comparable to those of the above two researchers, and some with better results in the majority of cases.     

Polynomial time approximation schemes for minimum disk cover problems

The following planar minimum disk cover problem is considered in this paper: given a set D\mathcal{D} of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within a factor of (1+ε) in O(mn^{O(\frac1e2log2\frac1e)})\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})}) time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem are considered and approximation schemes are designed.     

Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

In this paper we consider the constant rank unconstrained quadratic 0-1 optimization problem, CR-QP01 for short. This problem consists in minimizing the quadratic function 〈x, Ax〉 + 〈c, x〉 over the set {0,1} ⁿ where c is a vector in ℝ ⁿ and A is a symmetric real n × n matrix of constant rank r. We first present a pseudo-polynomial algorithm for solving the problem CR-QP01, which is known to be NP-hard already for r = 1. We then derive two new classes of special cases of the CR-QP01 which can be solved in polynomial time. These classes result from further restrictions on the matrix A. Finally we compare our algorithm with the algorithm of Allemand et al. (2001) for the CR-QP01 with negative semidefinite A and extend the range of applicability of the latter algorithm. It turns out that neither of the two algorithms dominates the other with respect to the class of instances which can be solved in polynomial time.     

Median problems with positive and negative weights on cycles and cacti

This paper deals with facility location problems on graphs with positive and negative vertex weights. We consider two different objective functions: In the first one (MWD) vertices with positive weight are assigned to the closest facility, whereas vertices with negative weight are assigned to the farthest facility. In the second one (WMD) all the vertices are assigned to the nearest facility. For the MWD model it is shown that there exists a finite set of points in the graph which contains the locations of facilities in an optimal solution. Furthermore, algorithms for both models for the 2-median problem on a cycle are developed. The algorithm for the MWD model runs in linear time, whereas the algorithm for the WMD model has a time complexity of  O(n²)\mathcal{O}(n^{2}) .     

An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al. (2001), Pisanti et al. (2003) and Pelfrêne et al. (2003), its output-polynomial time computability has been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n ³) time per motif with O(n) space, in particular O(n ³) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms. This work is done during the Hiroki Arimura’s visit in LIRIS, University Claude-Bernard Lyon 1, France.     

Constructing the Maximum Consensus Tree from Rooted Triples

We investigated the problem of constructing the maximum consensus tree from rooted triples. We showed the NP-hardness of the problem and developed exact and heuristic algorithms. The exact algorithm is based on the dynamic programming strategy and runs in O((m + n ²)3 ⁿ ) time and O(2 ⁿ ) space. The heuristic algorithms run in polynomial time and their performances are tested and shown by comparing with the optimal solutions. In the tests, the worst and average relative error ratios are 1.200 and 1.072 respectively. We also implemented the two heuristic algorithms proposed by Gasieniec et al. The experimental result shows that our heuristic algorithm is better than theirs in most of the tests.     

Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622–631; http://www.eng.tau.ac.il/amotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215–227, 1999) to its linear programming relaxation.     

On broadcasting in unicyclic graphs

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees. In this paper we present a linear algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph. As a byproduct, we find a broadcast center of the unicyclic graph. We also present an O(|V|+k ²) algorithm to find the broadcast time of an arbitrary unicyclic graph, where k is the length of the cycle. In the last section we give tight lower and upper bounds on broadcast time of a spanning tree based on the broadcast time of the unicyclic graph. The results of Sects. 2, 3 and most of the proofs in Sects. 2, 3 of this paper are presented by Harutyunyan and Maraachlian (Proceedings of 13th annual COCOON, pp. 372–383, 2007). All results in Sects. 4, 5 and the complete proof of Theorem 3 are new results.     

The application of a performance management system in hospitals: A hypothetical example

Abstract

The central theme of this article is performance management, defined as activities of organizations aimed at an effective and efficient use of their human resources. The organization focused on in particular is the hospital. Three principles taken from motivation theory are dealt with which are basic to performance management: goal setting, feedback and reinforcement. Next, a recently developed procedure (Pritchard 1990, Pritchard et al. 1988, 1989) for the design of performance management systems is described. This procedure, ProMES: Productivity Measurement and Enhancement Systems, is explained using a team of ward nurses as a hypothetical example. In addition to the nursing wards example, other potential applications of the ProMES technique to several hospitals areas are mentioned. Finally, some conditions that should be fulfilled in order to successfully start a ProMES project are discussed.     

An algorithm for optimal difference systems of sets

Difference Systems of Sets (DSS) are combinatorial structures that generalize cyclic difference sets and are used in code synchronization. A DSS is optimal if the associated code has minimum redundancy for the given block length n, alphabet size q, and error-correcting capacity ρ. An algorithm for finding optimal DSS is presented together with tables of optimal solutions found by this algorithm. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Research supported by NSF Grant CCR-0310632.