Abstract: Job shop scheduling problem in green manufact- uring not only aims to minimize the makespan and process cost, but also to decrease consumption of resource and negative effects on the environment. A Perti net model whose transitions are endowed with process time, process cost, resource consumption and negative effects on the environment is developed. The conflicts, which are caused by jobs sharing the same machine places in the model, are eliminated by arranging machining order for different jobs, and then a marked graph that stands for a feasible scheduling is derived. Three methods are proposed to produce a marked graph of feasible scheduling from another. A hybrid multi-objective heuristic which ingrates Mu-rata’s Multi-objective genetic algorithm and Czyzak’s Pareto simulated annealing algorithm is used to optimize the feasible scheduling. Numerical simulation demonstrates that the proposed heuristic is feasible and effective.

Key words: Green manufacturing, Job shop scheduling, Multi-objective genetic algorithm, Pareto simulated annealing algorithm, Petri net