Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Fluorimetric determination of intra- and extracellular free amino acids in the microalgae Tetraselmis gracilis (Prasinophyceae) using monolithic column in reversed phase mode

This paper describes the development and application of an RP HPLC method using a C(18) monolithic stationary phase for the separation and quantification of extra- and intracellular amino acids in a batch cultivation of the marine alga Tetraselmis gracilis. Fluorimetric detection was made after separation of the o-phthaldialdehyde 2-mercaptoethanol (OPA-2MCE) derivatives using a binary gradient elution. Separation of 19 amino acids was achieved with resolution >1.5 in about 39 min at a flow rate of 1.5 mL/min. RSD of analyses in seawater medium ranged from 0.36% for Orn (0.50 mu mol/L) to 12% for Ile (0.10 mu mol/L). The main constituents of the intracellular dissolved free amino acids (DFAAs) in the exponential growth phase were arginine (Arg), asparagine (Asn), alanine (Ala), aspartic acid (Asp), glutamic acid (Glu), serine (Ser), glycine (Gly), glutamine (Gln), and leucine (Leu). The major amino acids excreted to the media were valine (Val), Ala, Ser, and Gly. The monolithic phase facilitates the analysis by shortening the separation time and saving solvents and instrumentation costs (indeed conventional HPLC instrumentation can be used, running at lower pressures than those ones used with packed particle columns).

External polyacrylate-coating as alternative material for preparation of photopolymerized sol-gel monolithic column

Photopolymerized sol-gel monolithic columns for use in capillary electrochromatography were prepared in 125 mu m i.d. polyacrylate-coated fused-silica capillaries. The polyacrylate-coating, unlike the polyimide one, is transparent to the radiation used (approximate to 370 nm), and thus, no coating removal is necessary. This is a very important particularity since intrinsic capillary column characteristics, such as flexibility and mechanical resistance, are unchanged. A mixture containing metacryloxypropyltrimethoxysilane (MPTMS) as the polymeric precursor, hydrochloric acid as the catalyst, toluene as the porogen and bis(2,4,6-trimethylbenzoyl)-phenylphosphine oxide (Irgacure 819) as the photoinitiator was irradiated at 370 nm for 20 min inside the capillaries to prepare the columns through sol-gel approach. The versatility and viability of the use of polyacrilate as a new capillary external coating were shown through preparation of two columns under different conditions, which were tested in electrochromatography for separation of standard mixture containing thiourea (marker compound), propylbenzene, phenanthrene and pyrene. (C) 2008 Elsevier B.V. All rights reserved.

Quantitative ester analysis in cachaca and distilled spirits by gas chromatography-mass spectrometry (GC-MS)

An analytical procedure for the separation and quantification of ethyl acetate, ethyl butyrate, ethyl hexanoate, ethyl lactate, ethyl octanoate, ethyl nonanoate, ethyl decanoate, isoamyl octanoate, and ethyl laurate in cachaca, rum, and whisky by direct injection gas chromatography-mass spectrometry was developed. The analytical method is simple, selective, and appropriated for the determination of esters in distilled spirits. The limit of detection ranged from 29 (ethyl hexanoate) to 530 (ethyl acetate) mu g L-1, whereas the standard deviation for repeatability was between 0.774% (ethyl hexanoate) and 5.05% (isoamyl octanoate). Relative standard deviation values for accuracy vary from 90.3 to 98.5% for ethyl butyrate and ethyl acetate, respectively. Ethyl acetate was shown to be the major ester in cachaca (median content of 22.6 mg 100 mL(-1) anhydrous alcohol), followed by ethyl lactate (median content of 8.32 mg 100 mL(-1) anhydrous alcohol). Cachaca produced in copper and hybrid alembic present a higher content of ethyl acetate and ethyl lactate than those produced in a stainless-steel column, whereas cachaca produced by distillation in a stainless-steel column present a higher content of ethyl octanoate, ethyl decanoate, and ethyl laurate. As expected, ethyl acetate is the major ester in whiskey and rum, followed by ethyl lactate for samples of rum. Nevertheless, whiskey samples exhibit ethyl lactate at contents lower or at the same order of magnitude of the fatty esters.

Fluoxetine and norfluoxetine analysis by direct injection of human plasma in a column switching liquid chromatographic system

A column switching LC method is presented for the analysis of fluoxetine (FLU) and norfluoxetine (NFLU) by direct injection of human plasma using a lab-made restricted access media (RAM) column. A RAM-BSA-octadecyl silica (C-18) column (40 min x 4.6 mm, 10 mu m) is evaluated in both backflush and foreflush elution modes and coupled with a C-18 lab-made (50 mm x 4.6 mm, 3 pm) analytical column in order to perform online sample preparation. Direct injection of 100 mu L, of plasma samples is possible with the developed approach. In addition, reduction of sample handling is obtained when compared with traditional liquid-liquid extraction (LLE) and SPE. The total analysis time is around 20 min. A LOQ of 15 ng/mL is achieved in a concentration range of 15-500 ng/mL, allowing the therapeutic drug monitoring of clinical samples. The precision values achieved are lower than 15% for all the evaluated points with adequate recovery and accuracy. Furthermore, no matrix interferences are found in the analysis and the proposed method shows to be an adequate alternative for analysis of FLU in plasma.