Introducing preferences in scheduling applications. (January 2022)

• Record Type: Journal Article
• Authors: Srinath, Nitin; Yilmazlar, I. Ozan; Kurz, Mary E.; Taaffe, Kevin
• Is Part Of: Computers & industrial engineering. Volume 163(2022)
• Publication Date: 2022-01
• Subjects: Scheduling -- Sequence-dependent setup times -- MIP based heuristics -- Preferences -- Manufacturing optimization; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2021.107831
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: There is a need for sequence dependent preferences in some scheduling applications. These preferences can be modeled as objectives. MILPs are found to be viable only for small-sized problems. Heuristics based on insertion and bin-packing work well for larger problems. An MILP based heuristic performs better than all the other methods. Abstract: In some applications like fabric dying, the sequence in which jobs are processed on a single machine can influence product quality, i.e., there is a strong preference to run a certain type of job after another for reasons that do not influence regular scheduling objectives like total completion time. These reasons include minimizing changes in color families on machines (schedule preferences) and reducing the difference in shades between consecutive jobs (shade inconsistency). Nonetheless, the scheduling of jobs on machines must consider sequence-dependent setup times as well. In this paper, a mixed integer linear program has been presented to schedule jobs and account for setup times. The scheduling preferences and shade differences have been modeled as two new objectives, along with traditionally used objectives such as makespan, lateness and total setup time. The MILP is found to be useful only for small problems. To tackle larger problems, several heuristic methods are proposed. In order to obtain solutions quickly, multiple construction heuristics are developed based on SPT/LPT/EDD/LFJ rules and tested on a variety of industrially-inspired data sets. To produce schedules that perform well across multiple objectives at the same time, three additional tailored heuristics are developed. Both the original and tailored heuristics are compared to the optimal solutions for small-sized problems. In addition, a problem size reduction heuristic has been developed which can segment the larger MILP into smaller independently solvable MILPs by reducing the possible machines on which a job can be processed. For these larger problems, the heuristics are compared among themselves as well as against the problem size reduction heuristic.