This paper presents the fuzzy job shop scheduling problem with availability constraints. The objective is to find a schedule that maximizes the minimum agreement index subject to periodic maintenance, non-resumable jobs and fuzzy due-date. A random key genetic algorithm (RKGA) is proposed for the problem, in which a novel random key representation, a new decoding strategy incorporating maintenance operation and discrete crossover (DX) are used. RKGA is applied to some fuzzy scheduling problem with availability constraints and compared with other algorithms. Computational results show that RKGA performs better than other algorithms.
Fuzzy job shop scheduling problem (FJSSP) is the extension of job shop scheduling problem (JSSP). FJSSP has become the main research topic of production scheduling and some results have been obtained in the past decade. Kuroda and Wang (1996) discussed the static JSSP and dynamic JSSP with fuzzy information. A branch-and-bound algorithm is used to solve the static JSSP and the methods for dynamic JSSP are also considered. Sakawa and Mori (1999) presented an efficient genetic algorithm (GA) by incorporating the concept of similarity among individuals. Sakawa and Kubota (2000) presented a GA for multi-objective JSSP with fuzzy processing time and fuzzy due-date. Song, Zhu, Yin, and Li (2006) presented a combined strategy of GA and ant colony optimization. They also designed a new neighborhood search method and an improved tabu search to intensify the local search ability of the hybrid algorithm. Niu, Jiao, and Gu (2008) proposed a particle swarm optimization with genetic operators (GPSO) to minimize fuzzy makespan. Lei (2008) proposed an efficient Pareto archive particle swarm optimization for FJSSP with three objectives for obtaining a set of Pareto optimal solutions.
FJSSP with alternative process plan also attracts some attentions. Lei and Guo (2008) presented a two-population GA by using two-string representation and two independent populations. Lei (in press) developed an efficient decomposition–integration genetic algorithm for minimizing fuzzy makespan. Li, Zhu, Yin, and Song (2005) proposed a GA by adopting two-chromosome presentation and the extended version of Giffler–Thompson Procedure ( Giffler & Thompson, 1960).
Machine availability constraints mean that machines can be unavailable for preventive maintenance, periodic repair or random breakdown. These constraints have been considered in many scheduling problems, such as single machine ( Chen, 2009 and Graves and Lee, 1999), parallel machines ( Liao, Shyur, & Lin, 2005) and flow shop ( Allaoui and Artiba, 2006 and Allaoui et al., 2008). With respect to JSSP, Mauguière, Billaut, and Bouquard (2005) suggested a branch-and-bound algorithm to solve the single machine and JSSP with availability constraints and Gao, Gen, and Sun (2006) presented a hybrid GA to solve flexible JSSP with non-fixed availability constraints.
Machine availability constraints problems have been investigated extensively; however, for FJSSP, literature still assumes that machines are always available and availability constraints are seldom involved. The combination of FJSSP and availability constraints will make the considered problems be more close to the real-world situations. In this study, FJSSP with preventive maintenance (FJSSP-PM) is considered and an efficient RKGA is presented, which uses a random key representation and a decoding strategy incorporating maintenance operations. The chromosome of the presentation can be directly converted into an ordered operation list and a schedule is directly built by using the operation list. No special genetic operators are required and no illegal individuals occur in the search process of RKGA.
The remainder of the paper is organized as follows. The operations on fuzzy numbers are introduced in Section 2 and the problem formulation is done in Section 3. Section 4 describes a random key scheduling algorithm. Numerical test experiments on the proposed algorithm are reported in Section 5 and the conclusions are summarized in the final section.
Availability constraints such as preventive maintenance and random breakdown have been considered in single machine, parallel machines, flow shop, job shop, etc., however, availability constraints are seldom considered in fuzzy job shop. This paper presents a RKGA for the fuzzy scheduling problems with preventive maintenance by using a new representation and a decoding strategy. The chromosome of the representation can be easily converted into an ordered operation list and the maintenance operations are incorporated in the decoding procedure. Computational results demonstrate the good optimization ability of RKGA on fuzzy job shop scheduling with preventive maintenance.
For the scheduling problems with availability constraints, the main approaches are limited to the traditional programming method such as dynamic programming and heuristics, meta-heuristics such as genetic algorithm and tabu search are seldom applied to handle with these scheduling problems. Scheduling jobs and availability constraints in job shop or flexible job shop also attracts less attention. We will investigate these topics in the near future.
