{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:15:26Z","timestamp":1760145326799,"version":"build-2065373602"},"reference-count":32,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2024,7,6]],"date-time":"2024-07-06T00:00:00Z","timestamp":1720224000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100007595","name":"Belarusian Republican Foundation for Fundamental Research","doi-asserted-by":"publisher","award":["\u03a623PH\u03a6-017"],"award-info":[{"award-number":["\u03a623PH\u03a6-017"]}],"id":[{"id":"10.13039\/100007595","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We investigate relationships between scheduling problems with the bottleneck objective functions (minimising makespan or maximal lateness) and problems of optimal colourings of the mixed graphs. The investigated scheduling problems have integer durations of the multi-processor tasks (operations), integer release dates and integer due dates of the given jobs. In the studied scheduling problems, it is required to find an optimal schedule for processing the partially ordered operations, given that operation interruptions are allowed and indicated subsets of the unit-time operations must be processed simultaneously. First, we show that the input data for any considered scheduling problem can be completely determined by the corresponding mixed graph. Second, we prove that solvable scheduling problems can be reduced to problems of finding optimal colourings of corresponding mixed graphs. Third, finding an optimal colouring of the mixed graph is equivalent to the considered scheduling problem determined by the same mixed graph. Finally, due to the proven equivalence of the considered optimisation problems, most of the results that were proven for the optimal colourings of mixed graphs generate similar results for considered scheduling problems, and vice versa.<\/jats:p>","DOI":"10.3390\/a17070299","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T07:57:45Z","timestamp":1720425465000},"page":"299","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Mixed Graph Colouring as Scheduling a Partially Ordered Set of Interruptible Multi-Processor Tasks with Integer Due Dates"],"prefix":"10.3390","volume":"17","author":[{"given":"Evangelina I.","family":"Mihova","sequence":"first","affiliation":[{"name":"Mathematical Institute, Faculty of Mathematics, Computer Science and Statistics, Ludwig-Maximilians-Universitat Munich, Geschwister-Scholl-Platz, 1, 80539 Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9971-6169","authenticated-orcid":false,"given":"Yuri N.","family":"Sotskov","sequence":"additional","affiliation":[{"name":"United Institute of Informatics Problems, National Academy of Sciences, 6 Surganov Street, 220012 Minsk, Belarus"}]}],"member":"1968","published-online":{"date-parts":[[2024,7,6]]},"reference":[{"key":"ref_1","first-page":"289","article-title":"Mixed graph coloring for unit-time job-shop scheduling","volume":"2","author":"Sotskov","year":"2001","journal-title":"Int. J. Math. Algorithms"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1080\/0233193021000004994","article-title":"Scheduling problems and mixed graph colorings","volume":"51","author":"Sotskov","year":"2002","journal-title":"Optimization"},{"key":"ref_3","first-page":"20","article-title":"A chromatic polynomial of a mixed graph","volume":"6","author":"Sotskov","year":"1976","journal-title":"Vestsi Akad. Navuk BSSR Ser. Fiz. Mat. Navuk"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Miller, R.E., and Thatcher, J.W. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Brucker, P. (1995). Scheduling Algorithms, Springer.","DOI":"10.1007\/978-3-662-03088-2"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Harary, F. (1969). Graph Theory, Addison-Wesley. Reading.","DOI":"10.21236\/AD0705364"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Thulasiraman, K., and Swamy, M.N.S. (1992). Graphs: Theory and Algorithms, John Wiley & Sons, Inc.","DOI":"10.1002\/9781118033104"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF01194253","article-title":"Mixed graph colorings","volume":"45","author":"Hansen","year":"1997","journal-title":"Math. Methods Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.33581\/2520-6508-2021-2-67-81","article-title":"Mixed graph colouring as scheduling multi-processor tasks with equal processing times","volume":"2","author":"Sotskov","year":"2021","journal-title":"J. Belarusian State Univ. Math. Inform."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3625","DOI":"10.1016\/j.dam.2009.02.024","article-title":"A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints","volume":"157","author":"Giaro","year":"2009","journal-title":"Discret. Appl. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/0377-2217(94)00235-5","article-title":"Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard","volume":"89","author":"Hoogeveen","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Sotskov, Y.N., and Mihova, E.I. (2021). Scheduling multiprocessor tasks with equal processing times as a mixed graph coloring problem. Algorithms, 14.","DOI":"10.3390\/a14080246"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0012-365X(96)00208-7","article-title":"Restricted coloring models for timetabling","volume":"165\/166","year":"1997","journal-title":"Discret. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/S0166-218X(99)00019-0","article-title":"On a multiconstrained model for chromatic scheduling","volume":"94","year":"1999","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/s10878-019-00388-z","article-title":"Parameterized mixed graph coloring","volume":"38","author":"Damaschke","year":"2019","journal-title":"J. Comb. Optim."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1720","DOI":"10.1080\/00207543.2016.1224950","article-title":"Mixed graph coloring for unit-time scheduling","volume":"55","author":"Kouider","year":"2017","journal-title":"Int. J. Prod. Res."},{"key":"ref_17","first-page":"1001","article-title":"On minimization of memory usage in branch-and-bound algorithm for the mixed graph coloring: Application to the unit-time job shop scheduling","volume":"4967","author":"Kouider","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"105319","DOI":"10.1016\/j.cor.2021.105319","article-title":"A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: A mixed graph coloring approach","volume":"132","author":"Kouider","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1504\/IJMOR.2023.131397","article-title":"Scheduling preemptive jobs on parallel machines with a conflict graph: A graph multi-colouring approach","volume":"25","author":"Baaziz","year":"2023","journal-title":"Int. J. Math. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00373-013-1381-1","article-title":"On weak chromatic polynomials of mixed graphs","volume":"31","author":"Beck","year":"2015","journal-title":"Graphs Comb."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"108703","DOI":"10.1016\/j.knosys.2022.108703","article-title":"Improving local search for the weighted sum coloring problem using the branch-and-bound algorithm","volume":"246","author":"Niu","year":"2022","journal-title":"Knowl. Based Syst."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Jacqueline, O., Alden, M., Golshan, M., and Seyedamirabbas, M. (2021). Graph-based modeling in shop scheduling problems: Review and extensions. Appl. Sci., 11.","DOI":"10.3390\/app11114741"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"107721","DOI":"10.1016\/j.engappai.2023.107721","article-title":"Multi-product disassembly line balancing optimization method for high disassembly profit and low energy consumption with noise pollution constraints","volume":"130","author":"Liang","year":"2024","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"4260","DOI":"10.1109\/TSMC.2024.3376292","article-title":"A multiobjective scheduling of energy-efficient stochastic hybrid open shop with brain storm optimization and simulation evaluation","volume":"54","author":"Fu","year":"2024","journal-title":"IEEE Trans. Syst. Man Cybern. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1706","DOI":"10.1109\/TITS.2023.3315785","article-title":"Multi-objective home health care routing and scheduling with sharing service via a problem-specific knowledge-based artificial bee colony algorithm","volume":"25","author":"Fu","year":"2024","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"32","DOI":"10.23919\/CSMS.2022.0025","article-title":"A multi-objective scheduling and routing problem for home health care services via brain storm optimization","volume":"3","author":"Ma","year":"2023","journal-title":"Complex Syst. Model. Simul."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.laa.2022.01.022","article-title":"Some families of integral mixed graphs","volume":"641","author":"Andrade","year":"2022","journal-title":"Linear Algebra Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"104850","DOI":"10.1016\/j.cor.2019.104850","article-title":"A systematic study on meta-heuristic approaches for solving the graph coloring problem","volume":"120","author":"Mostafaie","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_29","first-page":"259","article-title":"New hybrid decentralized evolutionary approach for DIMACS challenge graph coloring & wireless network instances","volume":"4","author":"Balakrishnan","year":"2023","journal-title":"Int. J. Cogn. Comput. Eng."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.procs.2015.12.095","article-title":"Graph coloring based on evolutionary algorithms to support data hiding scheme on medical images","volume":"74","author":"Astuti","year":"2015","journal-title":"Procedia Comput. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"714","DOI":"10.1016\/j.procs.2015.08.223","article-title":"Acceleration based particle swarm optimization for graph coloring problem","volume":"60","author":"Agrawal","year":"2015","journal-title":"Procedia Comput. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1016\/j.procs.2018.08.024","article-title":"Genetic algorithm analysis using the graph coloring method for solving the university timetable problem","volume":"126","author":"Assi","year":"2018","journal-title":"Procedia Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/7\/299\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:11:10Z","timestamp":1760109070000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/7\/299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,6]]},"references-count":32,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2024,7]]}},"alternative-id":["a17070299"],"URL":"https:\/\/doi.org\/10.3390\/a17070299","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,7,6]]}}}