Solving certain singly constrained convex optimization problems in production planning

This paper considers the problem of minimizing a special convex function subject to one linear constraint. Based upon a theorem for lower and upper bounds on the Lagrange multiplier a fully polynomial time approximation scheme is proposed. The efficiency of the algorithm is demonstrated by a computational experiment.     

New directions in scheduling theory

This is an assessment of new developments in the theory of sequencing and scheduling. After a review of recent results and open questions within the traditional class of scheduling problems, we focus on the probabilistic analysis of scheduling algorithms and next discuss some extensions of the traditional problem class that seem to be of particular interest.     

On End-Extensions of Models of ¬exp

Every model of IΔ₀ is the tally part of a model of the stringlanguage theory Th-FO (a main feature of which consists in having induction on notation restricted to certain AC⁰. sets). We show how to “smoothly” introduce in Th-FO the binary length function, whereby it is possible to make exponential assumptions in models of Th-FO. These considerations entail that every model of IΔ₀ + ¬exp is a proper initial segment of a model of Th-FO and that a modicum of bounded collection is true in these models. Mathematics Subject Classification: 03F30, 03C62, 68Q15.     

How ∗ not ∗ to solve a Sudoku

We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.     

The Stock Market Model with Delayed Information Impact from a Socioeconomic View

Finding the critical factor and possible “Newton’s laws” in financial markets has been an important issue. However, with the development of information and communication technologies, financial models are becoming more realistic but complex, contradicting the objective law “Greatest truths are the simplest.” Therefore, this paper presents an evolutionary model independent of micro features and attempts to discover the most critical factor. In the model, information is the only critical factor, and stock price is the emergence of collective behavior. The statistical properties of the model are significantly similar to the real market. It also explains the correlations of stocks within an industry, which provides a new idea for studying critical factors and core structures in the financial markets.     

On single processor scheduling problems with learning dependent on the number of processed jobs

The importance of the role that learning plays in manufacturing, industry and computer systems is undeniable as well as the profit that can be increased if this phenomenon is taken into consideration for short- and long-term optimization. In this paper, we focus on scheduling jobs on a single processor, where its effectiveness can increase with the number of processed jobs, to minimize one of the following objectives: the maximum completion time with the release dates, the maximum lateness and the number of late jobs. It is proved that these well known polynomially solvable problems become at least NP-hard with the considered learning models. To solve them we provide some elimination procedures that are used to construct a branch and bound algorithm. Furthermore, we propose some fast heuristics for the problem of minimizing the number of late jobs with the general model of the learning effect.     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.     

Computation of the random arrival rule for bankruptcy problems

Bankruptcy problems are a fundamental class of fair division problems in microeconomics. Among the various solution concepts proposed for the problem, the random arrival rule is one of the most prominent. In this paper, we conduct a computational analysis of the rule. It is shown that the allocation returned by the rule is #P-complete to compute. The general complexity result is complemented by a pseudo-polynomial-time dynamic programming algorithm for the random arrival rule.