Abstract:

The single machine online scheduling problem with learning effect in prefabricated component production environment is provided to minimize the maximum weighted completion time in this paper. More precisely, it asks for an assignment of a series of independent prefabricated jobs arrived over time to a single machine, where the information of each prefabricated job including its basic processing time b_j, release time r_j, and positive weight w_j is unknown in advance and is disclosed upon the arrival of this job. And the actual processing time of prefabricated job J_j with learning effect is p_j = b_j(a − bt), where a and b are non-negative parameters and t is the starting time of prefabricated job J_j. In particular, a job may not be interrupted, i.e., preemptive is not allowed, and the machine can process at most one job at a time. Firstly, the off-line optimal schedule of the problem is analyzed. Then, we investigate this schedule model in the online environment where jobs arrive online over time. Fortunately, we propose a deterministic online algorithm, and show that the online algorithm is best possible with a competitive ratio of 2 − bb_min, where b_min = min {b_j|1 ≤ j ≤ n}. Furthermore, the effectiveness of the online algorithm is demonstrated by numerical experiments.

Key words: scheduling, single machine, online algorithm, learning effect, prefabricated components