University of Twente Student Theses

Login

The development of a generic scheduling approach for the PLANWISE optimizer

Alvarez, E.M. (2008) The development of a generic scheduling approach for the PLANWISE optimizer.

[img] PDF
770kB
Abstract:In this assignment, we focus on creating scheduling approaches for the optimizer in PLANWISE, a scheduling system created by ORTEC that supports the user in scheduling operations on different resources, such as machines and operators. The scheduling approaches must be able to solve a scheduling problem specified by the optimizer. In other words: The approaches must be able to create a schedule in which a set of operations is scheduled on a set of resources. The scheduling approaches have to meet two requirements: 1. The approaches should be generic and be able to handle different scheduling situations that occur in practice. 2. The approaches need to be able to handle manual adjustments made by users. More specifically: The approaches must be able to solve scheduling problems that contain fixed operations. These operations have already been scheduled on a set of resources and they may not be rescheduled: i.e. they may not be reassigned to different resources and they may not obtain different starting and completion times. To create scheduling approaches that meet these requirements, we first determine which scheduling problem the approaches should be able to solve. After considering the scheduling situations at different PLANWISE customers and potential customers, we create a general scheduling problem that contains the constraints and objectives mentioned most often by the PLANWISE customers. In the resulting scheduling problem, we have a set of jobs that each consist of one or more operations. These operations each need to be scheduled on a set of resources for their processing. The objective is now to schedule the operations on the available resources such that the total tardiness of the jobs in the schedule is minimized. The main constraints that we consider in our scheduling problem are general finish-start precedence relations, unique resources, preemptive and non-preemptive downtimes, setup times, routing constraints, resource-dependent processing times, and fixed operations. Subsequently, we determine which scheduling approaches we use to solve our scheduling problem. After performing a literature study on different scheduling approaches, we create two approaches to solve the general scheduling problem: One approach based on an integrated architecture and the regret-based random sampling algorithm and one approach based on the hierarchical architecture and local search algorithms. These approaches are able to handle the following constraints of the general scheduling problem: Finish-start precedence relations, unique resources, preemptive and non-preemptive downtimes, and setup times. The integrated approach is also able to handle routing constraints. In addition, we expect that the approaches are also able to handle fixed operations. We test both approaches on a set of scheduling instances and we subsequently compare the performance of the approaches to each other. In this comparison, we use the integrated approach as the benchmark approach, because ORTEC currently uses this approach in certain PLANWISE optimizers. Based on the test results, we can make a number of conclusions: First, on the tested instances the hierarchical approach generally performs better than the integrated approach with respect to tardiness minimization. Among the different versions of the hierarchical approach, we obtain the best results when we use simulated annealing to solve the assignment problem. In addition, a good initial solution and frequent iteration between the assignment and sequencing steps are also beneficial for the performance of the approach. 4 However, improvements can still be made to both approaches with respect to both tardiness minimization and calculation time. Based on test results, we are able to conclude that the characteristics of a scheduling instance have a lot of influence on the performance of the integrated approach. Specifically, the characteristics of the jobs in the scheduling instance have a lot of influence on the decision sets created to choose a next operation to schedule and the operation chosen from this decision set. Therefore, further research is required to fine tune the integrated approach to the scheduling instance. Also, further tests need to be done to determine the influence of the initial solution and communication scheme on the performance of the hierarchical approach. Finally, both approaches need to be adjusted so they are able to handle all constraints of the general scheduling problem: First, both approaches need to be adjusted so they can handle resource-dependent processing times. In addition, at present the approaches can only solve scheduling problems where all resources have the same intervals of preemptive downtime. In practice, however, resources often have different intervals of preemptive downtime. Finally,
Item Type:Essay (Master)
Clients:
ORTEC
Faculty:BMS: Behavioural, Management and Social Sciences
Subject:85 business administration, organizational science
Programme:Industrial Engineering and Management MSc (60029)
Link to this item:https://purl.utwente.nl/essays/59159
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page