一种组装线排序问题的启发式算法及其性能分析

A Heuristic for Assembly Scheduling Problem with Release Dates and Its Worst-Case Analysis

本文引进了工作带有准备时间的组装线排序问题.在第一阶段用 m 台机器来生产带有准备时间的工件的零部件,第二阶段用一台机器来组装这些零部件,目标是使总完工时间最小.我们给出了一个启发式算法,并证明了其最差情况性能比等于或小于8/3-1/m.

This paper introduces a two-stage assembly scheduling problem with release dates.There are m machines at the first stage each of which produces a component of a job with release dates.With all m components are available,a single assembly machine at the second stage completes the job.The objective is to schedule jobs on the machine so that the makespan is minimized.This problem has been proved to be NP-hard in the strong sense even when m=2. We present a heuristic for this problem with a worst- case ratio bound of 8/3 — 1/m.