Flat Panel Displays (FPDs) are manufactured using many pieces of different processing equipment arranged sequentially in a line. Although the constant inter-arrival time (i.e., the tact time) of glass substrates in the line should be kept as short as possible, the collision probability between glass substrates increases as tact time decreases. Since the glass substrate is expensive and fragile, collisions should be avoided. In this paper, we derive a closed form formula of the approximate collision probability for a model, in which the processing time on each piece of equipment is assumed to follow Erlang distribution. We also compare some numerical results of the closed form and computer simulation results of the collision probability.

Just-in-time scheduling problem is the problem of finding an optimal schedule such that each job finishes exactly at its due date. We study the problem under a realistic assumption called periodic time slots. In this paper, we prove that this problem cannot be approximated, assuming P≠NP. Next, we present a heuristic algorithm, assuming that the number of machines is one. The key idea is a reduction of the problem to a network flow problem. The heuristic algorithm is fast because its main part consists of computation of the minimum cost flow that dominates the total time. Our algorithm is O(n3) in the worst case, where n is the number of jobs. Next, we show some simulation results. Finally, we show cases in which our algorithm returns an optimal schedule and is a factor 1.5 approximation algorithm, respectively, and also give an approximation ratio depending on the upper bound of set-up times.

A job is called just-in-time if it is completed exactly on its due date. Under multi-slot conditions, each job has one due date per time slot and has to be completed just-in-time on one of its due dates. Moreover, each job has a certain weight per time slot. We would like to find a just-in-time schedule that maximizes the total weight under multi-slot conditions. In this paper, we prove that this problem is NP-hard.