Integrated production and outbound distribution scheduling problems with job release dates and deadlines

In this paper, we study an integrated production and outbound distribution scheduling model with one manufacturer and one customer. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to the customer. Each job has a release date and a delivery deadline. The objective of the problem is to issue a feasible integrated production and distribution schedule minimizing the transportation cost subject to the production release dates and delivery deadline constraints. We consider three problems with different ways how a job can be produced and delivered: non-splittable production and delivery (NSP–NSD) problem, splittable production and non-splittable delivery problem and splittable production and delivery problem. We provide polynomial-time algorithms that solve special cases of the problem. One of these algorithms allows us to compute a lower bound for the NP-hard problem NSP–NSD, which we use in a branch-and-bound (B&B) algorithm to solve problem NSP–NSD. The computational results show that the B&B algorithm outperforms a MILP formulation of the problem implemented on a commercial solver.     

Parsing Arabic using induced probabilistic context free grammar

The importance of the parsing task for NLP applications is well understood. However developing parsers remains difficult because of the complexity of the Arabic language. Most parsers are based on syntactic grammars that describe the syntactic structures of a language. The development of these grammars is laborious and time consuming. In this paper we present our method for building an Arabic parser based on an induced grammar, PCFG grammar. We first induce the PCFG grammar from an Arabic Treebank. Then, we implement the parser that assigns syntactic structure to each input sentence. The parser is tested on sentences extracted from the treebank (1650 sentences).We calculate the precision, recall and f-measure. Our experimental results showed the efficiency of the proposed parser for parsing modern standard Arabic sentences (Precision: 83.59 %, Recall: 82.98 % and F-measure: 83.23 %).     

Integrated production scheduling and batch delivery with fixed departure times and inventory holding costs

In this paper, we address a model for supply chain coordination. There are m manufacturers modelled as single machines, each of which processes a specific set of jobs (products). After processing is completed, jobs are batched, and batches are shipped to a customer by means of vehicles. The problem consists in concurrently finding a production schedule of the jobs, a partition of jobs into delivery batches and an assignment of delivery batches to vehicles, so that jobs are delivered within their deadlines and total costs are minimised. We focus on a scenario characterised by fixed departure times and inventory holding costs. For each departure time there is a given number of vehicles, possibly having limited capacity. Each job incurs a cost proportional to the time from job completion to delivery departure. In this paper, we show that the problem is NP-hard even for a very restricted case, and report various polynomiality results for two scenarios, namely: (i) when the production sequence of each manufacturer is fixed in advance, and (ii) when there is a single manufacturer and processing times are all equal to 1. We also point out several open problems.     

A power management system for energy harvesting and wireless sensor networks application based on a novel charge pump circuit

Energy Harvesting circuits are developed as an alternative solution to supply energy to autonomous sensor nodes in Wireless Sensor Networks. In this context, this paper presents a micro-power management system for multi energy sources based on a novel design of charge pump circuit to allow the total autonomy of self-powered sensors. This work proposes a low-voltage and high performance charge pump (CP) suitable for implementation in standard complementary metal oxide semiconductor (CMOS) technologies. The CP design was implemented using Cadence Virtuoso with AMS 0.35μm CMOS technology parameters. Its active area is 0.112 mm². Consistent results were obtained between the measured findings of the chip testing and the simulation results. The circuit can operate with an 800 mV supply and generate a boosted output voltage of 2.835 V with 1 MHz as frequency.     

Integrated production scheduling and vehicle routing problem with job splitting and delivery time windows

In this paper, we study a production scheduling and vehicle routing problem with job splitting and delivery time windows in a company working in the metal packaging industry. In this problem, a set of jobs has to be processed on unrelated parallel machines with job splitting and sequence-dependent setup time (cost). Then the finished products are delivered in batches to several customers with heterogeneous vehicles, subject to delivery time windows. The objective of production is to minimize the total setup cost and the objective of distribution is to minimize the transportation cost. We propose mathematical models for decentralized scheduling problems, where a production schedule and a distribution plan are built consecutively. We develop a two-phase iterative heuristic to solve the integrated scheduling problem. We evaluate the benefits of coordination through numerical experiments.     

A bibliography of non-deterministic lot-sizing models

Non-deterministic lot-sizing models are considered which serve for an explicit determination of lot sizes in an uncertain environment. Taxonomy components for such models are suggested and a bibliography structured according to these components is presented. The taxonomy components are numeric characteristics of a lot-sizing problem, names of uncertain parameters and names of approaches to model the uncertainty. The bibliography covers more than 300 publications since the year 2000.     

Buckling of a functionally graded coating with an embedded crack bonded to a homogeneous substrate

In an attempt to simulate buckling of nonuniform coatings, we consider the problem of an embedded crack in a functionally graded coating bonded to a homogeneous substrate subjected to a compressive loading. The coating is graded in the thickness direction and the material gradient is orthogonal to the crack direction which is parallel with the free surface. The loading consists of a uniform compressive strain applied away from the crack region. The graded coating is modeled as a nonhomogeneous medium with an isotropic stress-strain law. Using a nonlinear continuum theory and a suitable perturbation technique, the plane strain problem is reduced to an eigenvalue problem describing the onset of buckling. Using integral transforms, the resulting plane elasticity equations are converted analytically into singular integral equations which are solved numerically to give the critical buckling strain and the corresponding crack opening displacement shapes. The main objective of the paper is to study the influence of material nonhomogeneity on the buckling resistance of the graded layer for various crack positions and coating thicknesses.     

Minimizing the number of late jobs on a single machine under due date uncertainty

We study the problem of minimizing the number of late jobs on a single machine where job processing times are known precisely and due dates are uncertain. The uncertainty is captured through a set of scenarios. In this environment, an appropriate criterion to select a schedule is to find one with the best worst-case performance, which minimizes the maximum number of late jobs over all scenarios. For a variable number of scenarios and two distinct due dates over all scenarios, the problem is proved NP-hard in the strong sense and non-approximable in pseudo-polynomial time with approximation ratio less than 2. It is polynomially solvable if the number s of scenarios and the number v of distinct due dates over all scenarios are given constants. An O(nlog?n) time s-approximation algorithm is suggested for the general case, where n is the number of jobs, and a polynomial 3-approximation algorithm is suggested for the case of unit-time jobs and a constant number of scenarios. Furthermore, an O(n ^s+v?2/(v?1) ^v?2) time dynamic programming algorithm is presented for the case of unit-time jobs. The problem with unit-time jobs and the number of late jobs not exceeding a given constant value is solvable in polynomial time by an enumeration algorithm. The obtained results are related to a min-max assignment problem, an exact assignment problem and a multi-agent scheduling problem.     

A bicriteria two-machine flow-shop serial-batching scheduling problem with bounded batch size

We consider the two-machine flow-shop serial-batching scheduling problem where the machines have a limited capacity in terms of the number of jobs. Two criteria are considered here. The first criterion is the number of batches to be minimized. This criterion reflects situations where processing of any batch induces a fixed cost, which leads to a total cost proportional to the number of batches. The second criterion is the makespan. This model is relevant in different production contexts, especially when considering joint production and inbound delivery scheduling. We study the complexity of the problem and propose two polynomial-time approximation algorithms with a guaranteed performance. The effectiveness of these algorithms is evaluated using numerical experiments. Exact polynomial-time algorithms are also provided for some particular cases.