| Popis: |
Concurrent open shop problem can be viewed as the two-stage assemble-type flow shop (Lee et al., 1993) ignoring the second-stage assembling operation. Consider a set of jobs J = {1, 2, ..., n} and a set of machines M = {1, 2, ..., m}. Each job Ji is composed of tasks tik which have to be processed on specific machine k with processing time pik. Each job Ji has a weight wi and due date di. The major difference of this problem from the traditional open shop problem is that all tasks belong to the same job could be processed concurrently. Let Cik be the completion time of task of job i on machine k. The completion time of a job, Ci, is the greatest completion time among all of its tasks, i.e. Ci=max1 k m{Cik}. There are several variant applications in the production field (Roemer, 2006). The objective of minimizing the number of tardy jobs has been discussed extensively in different applications. In this chapter, we consider the concurrent open shop problem of minimizing the weighted number of tardy jobs. Following the three-field notation of Graham et al. (1979), we denote this problem by PD|| wiUi. To best of our knowledge, this problem was first proposed by Ahmadi and Bagchi (1990). Most works consider the objective Ci or wiCi. Roemer (2006) has done an extensive review on different objectives on this problem. Because this chapter discusses only the objective wiUi, we simply review the due date related results. The complexity result was first given by Wagneur and Sriskandarajah (1993). They have shown that even if there are only two machines, this problem is NP-hard. Leung et al. (21006) has shown that the PD|di=d| Ui is NP-hard and they proposed a Revised Hodgson-Moore algorithm to solve the PD|| Ui problem with agreeable conditions. Ng et al. (2003) introduced a negative approximation result of the PD|di=d, pik {0,1}| Ui problem. They also designed an LP-rounding algorithm with an error ratio of d+1 for the PD|di=d, pik {0,1}| wiUi problem. Ahmadi and Bagchi (1997) and Cheng et al. developed dynamic programming algorithms independently for PDm|| wiUi. Lin and Kononov (2006) have shown some negative approximation results for PD2|di=d| Ui and proposed an LP-based approximation algorithm for unweighted and weighted cases. The problem to minimize the weighted number of tardy jobs subject to a common due date is equivalent to the multiple-dimensional 1-0 knapsack problem. The number of machines could be |
