On-line algorithms for single machine scheduling with family setup times

The paper considers an on-line single machine scheduling problem where the goal is to minimize the makespan. The jobs are partitioned into families and a setup is performed every time the machine starts processing a batch of jobs of the same family. The scheduler is aware of the number of families and knows the setup time of each family, although information about a job only becomes available when that job is released. We give a lower bound on the competitive ratio of any on-line algorithm. Moreover, for the case of two families, we provide an algorithm with a competitive ratio that achieves this lower bound. As the number of families increases, the lower bound approaches 2, and we give a simple algorithm with a competitive ratio of 2.

Synthesis and enzymatic evaluation of the guanosine analogue 2-amino-6-mercapto-7-methylpurine ribonucleoside (MESG): insights into the phosphorolysis reaction mechanism based on the blueprint transition state: SN1 or SN2?

A modified experimental procedure for the synthesis of MESG (2-amino-6-mercapto-7-methylpurine ribonucleoside) 1 has been successfully performed and its full characterization is presented. High resolution ESI(+)-MSMS indicates both the nucleoside bond cleavage as the main fragmentation in the gas phase and a possible SN1 mechanism. Ab initio transition state calculations based on the blue print transition state support this mechanistic rationale and discard an alternative SN2 mechanism. Assays using purine nucleoside phosphorylase (PNP) enzyme (human and M. tuberculosis sources) indicate its efficiency in the phosphorolysis of MESG and allow the quantitative determination of inorganic phosphate in real time assay.