A Novel Disruptive Innovation-Like Algorithm for Single-Machine Scheduling with Sequence-Dependent Family Setup Times
Source abstract
Abstract
This paper proposes a novel disruptive innovation-like algorithm (DILA) for the problem of scheduling a single machine with sequence-dependent family setup times to minimize the total tardiness. The proposed algorithm is derived from Christensen’s (1997) theory of disruptive innovation. Based on this theory, a DILA is proposed, which first generates two initial populations: the mainstream market population and the emerging market population. Then, to improve the quality of solutions in the populations, three phases are created within a generation. Finally, the DILA allows the populations to evolve for several generations until the termination condition is met. Two populations constructed in DILA are to overcome the weakness of premature. In addition, two functions—the member-added function and member-removed function—implemented in DILA are added to increase the diversity. The DILA was tested on a dataset of 1440 observations from the literature. The computational results confirm that DILA is very effective.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Scheduling and Optimization Algorithms · Supply Chain and Inventory Management · Optimization and Search Problems
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Accounting Information, Takming University of Science and Technology, Taipei 11451, Taiwan
Funding
Ministry of Science and Technology, Taiwan
References (15)
Show source-provided references
1. Scheduling with product family set-up times: An application in TFT LCD manufacturing10.1080/00207540410001708461 ↗
2. Single machine scheduling with sequence-dependent family setups to minimize maximum lateness10.1057/jors.2009.63 ↗
3. A simulated annealing algorithm for single machine scheduling problems with family setups10.1016/j.cor.2008.08.001 ↗
4. Pinedo, M. (2002). Scheduling Theory, Algorithms, and Systems, Prentice-Hall. [2nd ed.].
5. Christensen, C.M. (1997). The Innovator’s Dilemma: When New Technologies Cause Great Firms to Fail, Harvard Business School Press.
6. Minimizing total tardiness on one machine is np-hard10.1287/moor.15.3.483 ↗
7. Heuristic procedures for scheduling job families with setups and due dates10.1002/(SICI)1520-6750(199912)46:8<978::AID-NAV7>3.0.CO;2-D ↗
8. A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness10.1016/j.ejor.2017.03.003 ↗
9. ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness10.1155/2016/9598041 ↗
10. Chantaravarapan, S., Gupta, J.N.D., and Smith, M.L. (2003, January 4–7). A hybrid genetic algorithm for minimizing total tardiness on a single machine with family setups. Proceedings of the Production and Operations Management Society Meeting (POMS ‘03), Savannah, GA, USA.
11. A heuristic to minimize the total weighted tardiness with sequence-dependent setups10.1080/07408179708966311 ↗
12. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem10.1016/j.ejor.2005.12.009 ↗
13. Grefenstette, J.J. (1985). Alleles, Loci and the TSP. Proceedings of the First International Conference on Genetic Algorithms and Their Applications, Lawrence Erlbaum.
14. Variable neighborhood search: Principles and applications10.1016/S0377-2217(00)00100-4 ↗
15. Iterated population-based VND algorithms for single-machine scheduling with sequence-dependent setup times10.1007/s00500-018-3014-3 ↗