Fast and effective algorithms for the liquid crystal display module (LCM) scheduling problem with sequence-dependent setup time

S. H. Chung, W.l. Pearn, Y. T. Tai

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The liquid crystal display module scheduling problem (LCMSP) is a variation of the classical parallel machines scheduling problem, which has many real-world applications, particular, in the thin film transistor liquid crystal display (TFT-LCD) manufacturing industry. In this paper, we present a case study on the LCMSP, which is taken from a final liquid crystal display module (LCM) shop floor in a TFT-LCD industry. For the case we investigated, the jobs are clustered by their product types and the machine setup time is sequentially dependent on the product types of the jobs processed on the machine. In LCMSP, the objective is to maximize the total profit subject to fulfilling contracted quantities without violating the due date and machine capacity restrictions. The LCMSP can be modelled as a multi-level optimization problem. The sub-problem of LCMSP can be transformed into the vehicle routing problem with time window (VRPTW). One can therefore solve the LCMSP efficiently using existing VRPTW algorithms. We present two new algorithms based on the savings algorithms with some modifications to accommodate the LCMSP. Based on the characteristics of the LCM process, a set of test problems is generated covering most of the real-world applications for test purposes. Computational results and performance comparisons show that the proposed algorithms solved the LCMSP efficiently and near-optimally.

Original languageEnglish
Pages (from-to)921-933
Number of pages13
JournalJournal of the Operational Research Society
Volume60
Issue number7
DOIs
StatePublished - 1 May 2009

Keywords

  • Parallel machines scheduling
  • Profit
  • Sequence dependence setup time

Fingerprint Dive into the research topics of 'Fast and effective algorithms for the liquid crystal display module (LCM) scheduling problem with sequence-dependent setup time'. Together they form a unique fingerprint.

Cite this