Applications of resource assignment and scheduling with Petri Nets and heuristic search

This paper introduces a new Petri Net based approach for resource allocation and scheduling. The goals are (i) minimize the number of required resources given a set of jobs, (ii) find both an assignment for all jobs in the span of a predefined shift and (iii) the sequence in which such jobs are executed. The studied problem was inspired from a complex real life manufacturing shop as described in this document. The modeling of the processes and jobs is carried out with Petri Nets due to their capability of representing dynamic, concurrent discrete-event dynamic systems. The resource assignment starts with an initial feasible solution (initial number of resources) and then follows with a re-optimization process aimed to further reduce the resource requirements. The algorithm is based on a modified Heuristic Search method previously presented. The algorithm was tested first on a number of instances from the literature and then on the aforementioned system (a car seat cover manufacturer). The proposed approach shows not only good results in terms of performance but also shows the potential of Petri Nets for modeling and optimizing real-life systems. An implementation phase at the first stages of the process is underway at the time of writing.     

A note ‘On a single machine-scheduling problem with separated position and resource effects’

This note concerns the paper [Janiak A, Kovalyov MY, Lichtenstein M. On a single machine-scheduling problem with separated position and resource effects. Optimization; 2013. doi:10.1080/02331934.2013.804077], which presents an analysis, a counterexample and a pseudocode related with our proof of optimality for a resource allocation algorithm given in [Rudek A, Rudek R. A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models. Comput. Math. Appl. 2011;62:1870–1878]. We show that the discussed analysis is based only on one part of our proof omitting its integral second part, which is the source of misunderstanding. The considered counterexample is applied for an algorithm, which was not the method presented in our paper, whereas our algorithm provides the correct result for the mentioned counterexample. The provided pseudocode of the resource allocation algorithm, which is presented as the correct method, is a pseudocode of the algorithm described in our paper. Therefore, we show that the results presented in our paper are correct.     

Heavy traffic resource pooling in parallel‐server systems

We consider a queueing system with r non‐identical servers working in parallel, exogenous arrivals into m different job classes, and linear holding costs for each class. Each arrival requires a single service, which may be provided by any of several different servers in our general formulation; the service time distribution depends on both the job class being processed and the server selected. The system manager seeks to minimize holding costs by dynamically scheduling waiting jobs onto available servers. A linear program involving only first‐moment data (average arrival rates and mean service times) is used to define heavy traffic for a system of this form, and also to articulate a condition of overlapping server capabilities which leads to resource pooling in the heavy traffic limit. Assuming that the latter condition holds, we rescale time and state space in standard fashion, then identify a Brownian control problem that is the formal heavy traffic limit of our rescaled scheduling problem. Because of the assumed overlap in server capabilities, the limiting Brownian control problem is effectively one‐dimensional, and it admits a pathwise optimal solution. That is, in the limiting Brownian control problem the multiple servers of our original model merge to form a single pool of service capacity, and there exists a dynamic control policy which minimizes cumulative cost incurred up to any time t with probability one. Interpreted in our original problem context, the Brownian solution suggests the following: virtually all backlogged work should be held in one particular job class, and all servers can and should be productively employed except when the total backlog is small. It is conjectured that such ideal system behavior can be approached using a family of relatively simple scheduling policies related to the cμ rule. This revised version was published online in June 2006 with corrections to the Cover Date.     

Three hierarchies of simple games parameterized by “resource” parameters

This paper contributes to the program of numerical characterization and classification of simple games outlined in the classic monograph of von Neumann and Morgenstern. We suggest three possible ways to classify simple games beyond the classes of weighted and roughly weighted games. To this end we introduce three hierarchies of games and prove some relationships between their classes. We prove that our hierarchies are true (i.e., infinite) hierarchies. In particular, they are strict in the sense that more of the key “resource” (which may, for example, be the size or structure of the “tie-breaking” region where the weights of the different coalitions are considered so close that we are allowed to specify either winningness or nonwinningness of the coalition) yields the flexibility to capture strictly more games.     

Scheduling unit — time tasks on flow — shops under resource constraints

We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log ₂ ² n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.     

Why are enterprise resource planning systems indispensable to supply chain management?

Supply chain design is becoming a core competency, and the enterprise resource planning (ERP) system is expected to be an integral component of supply chain management (SCM). Installing an ERP system is, however, expensive and risky. IT managers must decide how to use their limited resources and invest in the right product. Can an ERP system directly improve SCM competency? This study proposes a conceptual framework featuring the ERP benefits and SCM competencies, and examines the impacts of the former on the latter. The results confirm the operational, managerial, and strategic benefits of ERP for the SCM competencies, but not the IT infrastructure and organizational benefits as significant predictors of them. Moreover, more than 80% of respondents think it necessary to first adopt an ERP system as the backbone of company operations before deploying other enterprise systems (ES), such as the SCM system.     

A Stackelberg game model for resource allocation in cargo container security

This paper presents a game theoretic model that analyzes resource allocation strategies against an adaptive adversary to secure cargo container transportation. The defender allocates security resources that could interdict an unauthorized weapon insertion inside a container. The attacker observes the defender’s security strategy and chooses a site to insert the weapon. The attacker’s goal is to maximize the probability that the weapon reaches its target. The basic model includes a single container route. The results in the basic model suggest that in equilibrium the defender should maintain an equal level of physical security at each site on the cargo container’s route. Furthermore, the equilibrium levels of resources to interdict the weapon overseas increase as a function of the attacker’s capability to detonate the weapon remotely at a domestic seaport. Investment in domestic seaport security is highly sensitive to the attacker’s remote detonation capability as well. The general model that includes multiple container routes suggests that there is a trade-off between the security of foreign seaports and the physical security of sites including container transfer facilities, container yards, warehouses and truck rest areas. The defender has the flexibility to shift resources between non-intrusive inspections at foreign seaports and physical security of other sites on the container route. The equilibrium is also sensitive to the cost effectiveness of security investments.     

How is cultural influence manifested in the formation of mathematics textbooks? A comparative case study of resource book series between Shanghai and England

Focusing on issues about the development of mathematics textbooks from a cultural perspective, this study examined a widely-used curriculum resource series, One Lesson One Exercise, published in China, and its adapted English series, published in the UK, to explore how cultural influence is manifested in the two series of resource books. For the study we established a conceptual framework classifying culture into six types in relation to people’s beliefs, values and ways of interacting about them, for data collection and analysis. The results indicate that there exist considerable differences between the Chinese and the English series that are related to cultural factors. It appears that, to a large extent, culture plays an essential role in the development of mathematics textbooks. Concerning the different types of culture, the results show that most adaptations between the Chinese series and the English series are related to ‘ways of behaving and customs’ and ‘artifacts, flora and fauna’, followed by ‘identities’ and ‘geography’, and the least are related to ‘organisations’ and ‘history’. Based on the study, we argue that the relevance and importance of culture to the development of mathematics textbooks must not be underestimated, and more research in this direction is needed.     

Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem

In the past decades, resource parameters have been introduced in project scheduling literature to measure the scarceness of resources of a project instance. In this paper, we incorporate these resource scarceness parameters in the search process to solve the multi-mode resource constrained project scheduling problem, in which multiple execution modes are available for each activity in the project. Therefore, we propose a scatter search algorithm, which is executed with different improvement methods, each tailored to the specific characteristics of different renewable and nonrenewable resource scarceness values. Computational results prove the effectiveness of the improvement methods and reveal that the procedure is among the best performing competitive algorithms in the open literature.     

Tabu search for discrete–continuous scheduling problems with heuristic continuous resource allocation

Problems of scheduling non-preemptable, independent jobs on parallel identical machines under an additional continuous renewable resource to minimize the makespan are considered. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. The processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic procedure for allocating the continuous resource is used. The tabu search metaheuristic to solve the considered problem is presented. The results produced by tabu search are compared with optimal solutions for small instances, as well as with the results generated by simple search methods – multi-start iterative improvement and random sampling for larger instances.     

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

Hybrid defensive resource allocations in the face of partially strategic attackers in a sequential defender–attacker game

Many models have been developed to study homeland security games between governments (defender) and terrorists (attacker, adversary, enemy), with the limiting assumption of the terrorists being rational or strategic. In this paper, we develop a novel hybrid model in which a centralized government allocates defensive resources among multiple potential targets to minimize total expected loss, in the face of a terrorist being either strategic or non-strategic. The attack probabilities of a strategic terrorist are endogenously determined in the model, while the attack probabilities of a non-strategic terrorist are exogenously provided. We study the robustness of defensive resource allocations by comparing the government’s total expected losses when: (a) the government knows the probability that the terrorist is strategic; (b) the government falsely believes that the terrorist is fully strategic, when the terrorist could be non-strategic; and (c) the government falsely believes that the terrorist is fully non-strategic, when the terrorist could be strategic. Besides providing six theorems to highlight the general results, we find that game models are generally preferred to non-game model even when the probability of a non-strategic terrorist is significantly greater than 50%. We conclude that defensive resource allocations based on game-theoretic models would not incur too much additional expected loss and thus more preferred, as compared to non-game-theoretic models.     

δ - and δ ′-shocks and the transportation and concentration processes

Using the definitions of δ - and δ ′-shocks for some systems of conservation laws, the corresponding Rankine–Hugoniot conditions are derived. We also derive the balance laws describing area, volume, mass and momentum transportation between the area outside the wave front and the wave front. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Soft clustering – Fuzzy and rough approaches and their extensions and derivatives

Clustering is one of the most widely used approaches in data mining with real life applications in virtually any domain. The huge interest in clustering has led to a possibly three-digit number of algorithms with the k-means family probably the most widely used group of methods. Besides classic bivalent approaches, clustering algorithms belonging to the domain of soft computing have been proposed and successfully applied in the past four decades. Bezdek’s fuzzy c-means is a prominent example for such soft computing cluster algorithms with many effective real life applications. More recently, Lingras and West enriched this area by introducing rough k-means. In this article we compare k-means to fuzzy c-means and rough k-means as important representatives of soft clustering. On the basis of this comparison, we then survey important extensions and derivatives of these algorithms; our particular interest here is on hybrid clustering, merging fuzzy and rough concepts. We also give some examples where k-means, rough k-means, and fuzzy c-means have been used in studies.     

Quasipower and hypergeometric series — construction and evaluation

It is proved that some power series converging very slowly in a neighbourhood of the point 1 can be transformed intoquasipower series. The latter converge faster but are more complicated because they contain some hypergeometric series₂ F ₁. Standard methods of the values evaluation for needed hypergeometric series with the aid of recurrence relations are not sufficiently efficient for some variable values. Therefore a new method, formally similar to Levin's transforms, is proposed. More generally, this is a method of approximative evaluating of such a solution of an inhomogeneous recurrence relation of order one which has some particular asymptotic properties.The efficacity of the proposed methods is analyzed in detail for Euler's dilogarithm. This is a typical function whose power series is approached with difficulties ifz1. In particular, its Padé approximants are sufficiently accurate only for, sayx[–1, 1/2]. Hermite-Padé approximation is more effective. Resulting irrational approximants generalize in some sense partial sums of the quasipower series introduced here.     

Lot sizing and scheduling — Survey and extensions

This contribution summarizes recent work in the field of lot sizing and scheduling. The objective is not to give a comprehensive literature survey, but to explain differences of formal models and to provide some first readings recommendations. Our focus is on capacitated, dynamic, and deterministic cases. To underscore the importance of the research efforts, current practice is described and its shortcomings are exposed. Mathematical programming models where the planning horizon is subdivided into several discrete periods are given for both approaches that are well-established and approaches which may represent tomorrow's state of the art. Two research directions are discussed in more detail: continuous time models and multi-level lot sizing and scheduling. The paper concludes with some advice for future research activities.     

E—matrices and Several Necessary and Sufficient Conditions

AER-x.,Aiscalledanonnegative(nonPositive)matrixifau>O(a,jO(aiirtO),markedA>O(AO(i#j),auO,wecallp(A)=max{IA,l,lA,l'.-.,lAnl},(whereA,,A2,..',A"areeigenva1ueofA)asspectralradiusofA.LemmalIfAe7'.,thenareanonnegativesquarematrxBandapositivenumberksuchthatA=B-kI(whereIistheidentitymatrixofordern).ProofLetbti=…     

Structure and Application of Algebraic Spline Curve and Surface

Algebraic-geometry foundations for non-linear spline functions are estab-lished.The structure of algebraic spline curves and surfaces represented by implicitforms are investigated.The necessary and sufficient conditions for smooth connection ofalgebraic curves(or surfaces)are presented.     

Problem-Solving and Sequence

In 1971,the famous mathematician George Polya,introduced four basic steps or phases for solving problems: Step1 Understand the Problem Step2 Decide on a Plan Step 3 Carry out the Plan Step4 Look Back