Observation of C60 film formation on a highly oriented pyrolitic graphite substrate via scanning tunnelling microscopy

We have investigated the early stages in the adsorption process of C60 molecules on a highly oriented pyrolitic graphite (HOPG) substrate. C60 powder was thermally evaporated in UHV of 10−8 Pa conditions onto a freshly cleaved HOPG surface. We did not observe individual fullerenes on the substrate for the case of short deposition times and low evaporation rates. However, small islands of C60 molecules with an fcc structure could be observed when the deposition rate was about 0.2 nm/min and the total thickness was above 1 nm. The islands did not grow in the vicinity of the HOPG steps. The typical lateral dimensions of these islands were of the order of a few hundred square nanometers, having thickness of up to five monolayers. We modified the shapes and positions of these islands by the STM tip, using a small (less than 1 V) bias voltage.

Heuristics for short route job shop scheduling problems

We consider two “minimum”NP-hard job shop scheduling problems to minimize the makespan. In one of the problems every job has to be processed on at most two out of three available machines. In the other problem there are two machines, and a job may visit one of the machines twice. For each problem, we define a class of heuristic schedules in which certain subsets of operations are kept as blocks on the corresponding machines. We show that for each problem the value of the makespan of the best schedule in that class cannot be less than 3/2 times the optimal value, and present algorithms that guarantee a worst-case ratio of 3/2.