Multi-Periods Job-Shop Scheduling Problem

C. Duhamel	J. Fontanel	P. Lacomme	P. Pelissier	N. Tchernev

I. Description

This paper addresses the multi-period multi products job-shop scheduling problem. At each period the shop has a limited capacity and each product has a given demand. This problem is generalizations of the job-shop scheduling problem where several job-shops must be solve tackling a maximal finish time. The number of periods considered is denoted and is designates the bound of the schedule horizon. For each period the objective consists in defining if a job-shop solution exists such that all job finished dates are upper bounded by the period capacity and when no solution exists to determine which job must be deleted in the period and forwarded to a previous one. A storage costs and a production costs are addressed to evaluate the global costs of a solution. The multi-period multi products job-shop scheduling problem is a step forwards the MRP II in classical computer aided manufacturing management system. The Job-Shop Scheduling Problem (JSSP) is a well-known optimization problem often used in practical scheduling applications in the manufacturing sector. The JSSP can be formulated as follows: a set of jobs has to be processed on a set of machines . Each job is fully defined by an ordered (linear) sequence of operations that are associated with a particular machine. Therefore, the dimension of the problem is often denoted as . In addition, the JSSP must satisfy other constraints such as: (i) no more than one operation of any job can be executed simultaneously; (ii) no machine can process more than one operation at the same time; (iii) the job operations must be executed in a predefined sequence and once an operation is started, no preemption is permitted.

Each operation is associated with a particular job and machine and has a duration . The objective is to schedule each operation on the machines, taking the precedence constraints into account such that the total makespan () is minimized. The Multi Period Job-Shop Scheduling Problem consists in Job-Shop Scheduling Problems which must be solved consecutively trying to access to a makespan less than the capacity of the period. The capacity represents a number of units of time available for processing and a job-shop solution is stated as feasible if the makespan (the completion time of the last operation) is less than the capacity. For each period we consider a production cost in euros per jobs and for each job, storage cost in euros per unit of time per job. This problem is close to the problem of integration of lot sizing and scheduling problems formulated by [1] [2]. The problem consists in defining a job-shop solution for each period and determining which job must be backwarded.

II. File description:

III. Instances:

Instances	Description	Number of periods	Number of jobs	Download Instances	Download Solutions
LA01-JSSP	Based on Lawrence instance LA01	6	68
LA02-JSSP	Based on Lawrence instance LA02	6	66
LA03-JSSP	Based on Lawrence instance LA03	6	55
LA04-JSSP	Based on Lawrence instance LA04	6	67
LA05-JSSP	Based on Lawrence instance LA05	6	58
LA06-JSSP	Based on Lawrence instance LA06	6	64
LA07-JSSP	Based on Lawrence instance LA07	6	86
LA08-JSSP	Based on Lawrence instance LA08	6	Come soon
LA09-JSSP	Based on Lawrence instance LA09	6	Come soon
LA10-JSSP	Based on Lawrence instance LA10	6	Come soon
LA01-10-JSSP	Instances LA01 to LA10-JSSP	/	/

IV. Reference:

[1] S. Dauzère-Pérès and J.B. Lasserre. Integration of lot sizing and scheduling decisions in a job-shop. European Journal of Operational Research, 75(2):413-426, 1994.

[2] S. Dauzère-Pérès, J.B. Lasserre, An Integrated Approach in Production Planning and Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, 1994.

[3] Bierwirth C. A generalized permutation approach to jobshop scheduling with genetic algorithms. OR Spektrum. Vol. 17, pp. 87-92, 1995

[4] Nowicky E. and C. Smutnicki. A fast taboo search algorithm for the job-shop problem. Management Science. 42 (6). 797-813. 2006.