M. Sc. Andreas Hipp (Chair of Business Administration, HSU)
Machine wear and tear is a typical problem that must be dealt with in real-world production environments. In scheduling research since the 1980s, time-dependent deterioration is usually identified as the main factor for machine wear. In our work, we focus on machine deterioration that is not primarily influenced by time, but by the number of jobs. Each job, regardless of its processing time, leads to the same deterioration, which is tantamount to position-dependent (pd) maintenance. After a given number of jobs, the machine is completely worn out and must be restored by performing a maintenance operation of fixed length. This maintenance operation can also be performed earlier, which leads to the same effect for the machine – it is completely restored. In general, pd maintenance is relevant to any real-world setting where the number of jobs causes the main deterioration and not their length, such as the wear and tear of batteries in automobiles with combustion engines or the landing gear of aircrafts. So far, only a few studies have addressed scheduling problems with pd maintenance yet, see, e.g., Drozdowski et al. (2017), who introduce this type of deterioration.
In this project, we deal with the single machine scheduling problem of minimizing the total weighted completion time with ready times, weights and uniform processing times for all jobs. This layout is solvable in polynomial time, but the solution approach, a dynamic program, is characterized by a runtime of O(n18). The runtime is caused by a large number of states per iteration, which in turn are caused by the jobs’ ready times that make the sequencing more complex, and numerous options to schedule maintenance operations before/after or with a considered job.
An initial code implemented in Python by our research group can only solve very small instances in reasonable time. The applied testbed is provided by Drozdowski et al. (2016) and modified for the studied problem. Together with the hpc.bw project group at the Helmut Schmidt University, we aim to find ways to improve the code or even the formulation of the dynamic program by testing options to reduce the code, applying libraries to fasten the procedure, or finding ways to parallelize parts of the algorithm. Finally, we want to gain learning effects for our next projects dealing with similar scheduling problems.